ROOM 3433

*G*is (0,1)-colorable if

*V(G)*can be partitioned into two sets

*V*and

_{0}*V*so that

_{1}*G*[

*V*] is an independent set and

_{0}*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.

_{1}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.

Tags: 김재훈