Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
9516097 | Journal of Combinatorial Theory, Series B | 2005 | 25 Pages |
Abstract
Wegner conjectured that the chromatic number of the square of any planar graph G with maximum degree Î⩾8 is bounded by Ï(G2)⩽â32Îâ+1. We prove the bound Ï(G2)⩽â53Îâ+78. This is asymptotically an improvement on the previously best-known bound. For large values of Î we give the bound of Ï(G2)⩽â53Îâ+25. We generalize this result to L(p,q)-labeling of planar graphs, by showing that λqp(G)⩽qâ53Îâ+18p+77q-18. For each of the results, the proof provides a quadratic time algorithm.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Michael Molloy, Mohammad R. Salavatipour,