Coloring squares of planar graphs with girth six
Coloring squares of planar graphs with girth six
复制标题
DOI：
10.1016/j.ejc.2007.11.005
复制
发表时间：
2008-05
期刊：
影响因子：
--
通讯作者：
Zdenek Dvorák;D. Král;P. Nejedlý;R. Škrekovski
中科院分区：
文献类型：
--
作者：
Zdenek Dvorák;D. Král;P. Nejedlý;R. Škrekovski
Wang和Lih推测，对于每一个g≥5，存在一个数M(g)，使得周长至少为g且最大度数Δ≥M(g)的平面图g的平方是（Δ+1）可着色的。已知当g≥7时该猜想为真，但当g∈{5,6}时该猜想为假。我们证明了g=6的猜想只差一个，即周长至少为6且足够大的最大度的平面图g的平方是（Δ+2）可着色的。
Wang and Lih conjectured that for every g≥5, there exists a number M(g) such that the square of a planar graph G of girth at least g and maximum degree Δ≥M(g) is (Δ+1)-colorable. The conjecture is known to be true for g≥7 but false for g∈{5,6}. We show that the conjecture for g=6 is off by just one, i.e., the square of a planar graph G of girth at least six and sufficiently large maximum degree is (Δ+2)-colorable.