KAIST Discrete Math Seminar

A graph G is (0,1)-colorable if V(G) can be partitioned into two sets V₀ and V₁ so that G[V₀] is an independent set and G[V₁] has maximum degree at most 1. The problem of verifying whether a graph is (0,1)-colorable is NP-complete even in the class of planar graphs of girth 9.

Maximum average degree, Mad(G), is a graph parameter measuring how sparse the graph G is. Borodin and Kostochka showed that every graph G with Mad(G) ≤ 12/5 is (0,1)-colorable, thus every planar graph with girth at least 12 also is (0,1)-colorable.

The aim of this talk is to prove that every triangle-free graph G with Mad(G) ≤ 22/9 is (0,1)-colorable. We prove the slightly stronger statement that every triangle-free graph G with |E(H)| < (11|V(H)|+5)/9 for every subgraph H is (0,1)-colorable and show that there are infinitely many non (0,1)-colorable graphs G with |E(G)|= (11|V(G)|+5)/9.

This is joint work with A. V. Kostochka and Xuding Zhu.