Publication details
Coloring squares of planar graphs with girth six
| Authors | |
|---|---|
| Year of publication | 2008 |
| Type | Article in Periodical |
| Magazine / Source | European Journal of Combinatorics |
| Citation | |
| Doi | http://dx.doi.org/10.1016/j.ejc.2007.11.005 |
| Description | 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 Delta >= M(g) is (Delta + 1)-colorable. The conjecture is known to be true for g >= 7 but false for g is an element of {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 (Delta + 2)-colorable. (c) 2007 Elsevier Ltd. All rights reserved. |