Coloring triangle-free graphs on surfaces

DVORAK, Z; Daniel KRÁĽ a R THOMAS. Coloring triangle-free graphs on surfaces. PHILADELPHIA: SIAM, 2009, s. "120"-"+", 2 s.

Základní údaje

Originální název

Coloring triangle-free graphs on surfaces

Autoři

DVORAK, Z; Daniel KRÁĽ a R THOMAS

Vydání

PHILADELPHIA, SIAM, 2009

---

Další údaje

Jazyk

angličtina

Typ výsledku

Článek v odborném periodiku

Utajení

není předmětem státního či obchodního tajemství

Označené pro přenos do RIV

Ne

UT WoS

000281447000014

---

Anotace

V originále

Gimbel and Thomassen asked whether 3-colorability of a triangle-free graph drawn on a fixed surface can be tested in polynomial time. We settle the question by giving a linear-time algorithm for every surface which combined with previous results gives a linear-time algorithm to compute the chromatic number of such graphs. Our algorithm is based on a structure theorem that for a triangle-free graph drawn on a surface Sigma guarantees the existence of a subgraph H, whose size depends only on Sigma, such that there is an easy test whether a 3-coloring of H extends to a 3-coloring of G. The test is based on a topological obstruction, called the "winding number" of a 3-coloring. To prove the structure theorem we make use of disjoint paths with specified ends to find a 3-coloring. If the input triangle-free graph G drawn in Sigma is 3-colorable we can find a 3-coloring in quadratic time, and if G quadrangulates Sigma then we can find the 3-coloring in linear time. The latter algorithm requires two ingredients that may be of independent interest: a generalization of a data structure of Kowalik and Kurowski to weighted graphs and a speedup of a disjoint paths algorithm of Robertson and Seymour to linear time.