• search hit 17 of 28
Back to Result List

Coloring semirandom graphs optimally

Please always quote using this URN:urn:nbn:de:0296-matheon-2792
  • We study semirandom k-colorable graphs made up as follows. Partition the vertex set V = {1, ... , n} randomly into k classes V1, ... , Vk of equal size and include each Vi-Vj -edge with probability p independently (1 ≤ i < j ≤ k) to obtain a graph G0. Then, an adversary may add further Vi-Vj -edges (i 6= j) to G0, thereby completing the semirandom graph G = G ∗ n,p,k. We show that if np ≥ max{(1 + ε)k ln n,C0k2} for a certain constant C0 > 0 and an arbitrarily small but constant ε > 0, an optimal coloring of G ∗ n,p,k can be found in polynomial time with high probability. Furthermore, if np ≥ C0 max{k ln n, k2}, a k-coloring of G ∗ n,p,k can be computed in polynomial expected time. Moreover, an optimal coloring of G ∗ n,p,k can be computed in expected polynomial time if k ≤ ln1/3 n and np ≥ C0k ln n. By contrast, it is NP-hard to k-color G ∗ n,p,k w.h.p. if np ≤ (1/2 − ε)k ln(n/k).

Download full text files

Export metadata

Additional Services

Share in Twitter Search Google Scholar
Metadaten
Author:Amin Coja-Oghlan
URN:urn:nbn:de:0296-matheon-2792
Referee:Hans Jürgen Prömel
Document Type:Preprint, Research Center Matheon
Language:English
Date of first Publication:2005/05/11
Release Date:2005/10/31
Institute:Humboldt-Universität zu Berlin
Preprint Number:277
Verstanden ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.