Informace o publikaci
Coloring squares of planar graphs with girth six
| Autoři | |
|---|---|
| Rok publikování | 2008 |
| Druh | Článek v odborném periodiku |
| Časopis / Zdroj | European Journal of Combinatorics |
| Citace | |
| Doi | http://dx.doi.org/10.1016/j.ejc.2007.11.005 |
| Popis | 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. |