TY - GEN A1 - Coja-Oghlan, Amin T1 - Coloring semirandom graphs optimally N2 - 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). Y1 - 2005 UR - https://opus4.kobv.de/opus4-matheon/frontdoor/index/index/docId/279 UR - https://nbn-resolving.org/urn:nbn:de:0296-matheon-2792 ER -