A unified approach to distance-two colouring of planar graphs

ABSTRACT

We introduce the notion of (A, B)-colouring of a graph: For given vertex sets A, B, this is a colouring of the vertices in B so that both adjacent vertices and vertices with a common neighbour in A receive different colours. This concept generalises the notion of colouring the square of graphs and of cyclic colouring of plane graphs. We prove a general result which implies asymptotic versions of Wegner's and Borodin's Conjecture on these two colourings. Using a recent approach of Havet et al., we reduce the problem to edge-colouring of multigraphs and then use Kahn's result that the list chromatic index is close from the fractional chromatic index.

Our results are based on a strong structural lemma for planar graphs which also implies that the size of a clique in the square of a planar graph of maximum degree Δ is at most 3/2 Δ plus a constant.

REFERENCES

• 1: Geir Agnarsson , Magnús M. Halldórsson, Coloring Powers of Planar Graphs, SIAM Journal on Discrete Mathematics, v.16 n.4, p.651-662, 2003 [doi>10.1137/S0895480100367950]
• 2: O. Amini, L. Esperet, and J. van den Heuvel, A unified approach to distance-two colouring of planar graphs. In preparation.
• 3: O. Amini, B. Reed, and B. Shepherd, Algorithms for hardcore distributions. In preparation.
• 4: O. V. Borodin, Solution of the Ringel problem on vertex-face coloring of planar graphs and coloring of 1-planar graphs (in Russian). Metody Diskret. Analyz. 41 (1984), 12--26.
• 5: O. V. Borodin, H. J. Broersma, A. Glebov, and J. van den Heuvel, Minimal degrees and chromatic numbers of squares of planar graphs (in Russian). Diskretn. Anal. Issled. Oper. Ser. 1 8, no. 4 (2001), 9--33.
• 6: O. V. Borodin , H. J. Broersma , A. Glebov , J. van den Heuvel, A new upper bound on the cyclic chromatic number, Journal of Graph Theory, v.54 n.1, p.58-72, January 2007 [doi>10.1002/jgt.v54:1]
• 7: O. V. Borodin, D. P. Sanders, and Y. Zhao, On cyclic colorings and their generalizations. Discrete Math. 203 (1999), 23--40.
• 8: J. Edmonds, Maximum matching and a polyhedron with 0, 1-vertices. J. Res. Nat. Bur. Standards Sect. B 69B (1965), 125--130.
• 9: F. Havet, J. van den Heuvel, C. McDiarmid, and B. Reed, List colouring squares of planar graphs. Preprint (2008).
• 10: T. J. Hetherington and D. R. Woodall, List-colouring the square of a K₄-minor-free graph. Discrete Math. (2007). Available online: doi:10.1016/j.disc.2007.07.10.
• 11: Jan van den Heuvel , Sean McGuinness, Coloring the square of a planar graph, Journal of Graph Theory, v.42 n.2, p.110-124, February 2003 [doi>10.1002/jgt.v42:2]
• 12: T. R. Jensen and B. Toft, Graph Coloring Problems. John-Wiley & Sons, New York, 1995.
• 13: T. K. Jonas, Graph coloring analogues with a condition at distance two: L(2, 1)-labelings and list λ-labelings. Ph.D. Thesis, University of South Carolina, 1993.
• 14: Jeff Kahn, Asymptotics of the list-chromatic index for multigraphs, Random Structures & Algorithms, v.17 n.2, p.117-156, Sept. 2000 [doi>10.1002/1098-2418(200009)17:2<117::AID-RSA3>3.0.CO;2-9]
• 15: Alexandr V. Kostochka , Douglas R. Woodall, Choosability conjectures and multicircuits, Discrete Mathematics, v.240 n.1-3, p.123-143, September 28 2001 [doi>10.1016/S0012-365X(00)00371-X]
• 16: Ko-Wei Lih , Wei-Fan Wang , Xuding Zhu, Note: coloring the square of a K4-minor free graph, Discrete Mathematics, v.269 n.1-3, p.303-309, 28 July 2003 [doi>10.1016/S0012-365X(03)00059-1]
• 17: Michael Molloy , Mohammad R. Salavatipour, A bound on the chromatic number of the square of a planar graph, Journal of Combinatorial Theory Series B, v.94 n.2, p.189-213, July 2005 [doi>10.1016/j.jctb.2004.12.005]
• 18: O. Ore and M. D. Plummer, Cyclic coloration of plane graphs. In: Recent Progress in Combinatorics; Proceedings of the Third Waterloo Conference on Combinatorics. Academic Press, San Diego (1969) 287--293.
• 19: Daniel P. Sanders , Yue Zhao, A new bound on the cyclic chromatic number, Journal of Combinatorial Theory Series B, v.83 n.1, p.102-111, September 2001 [doi>10.1006/jctb.2001.2046]
• 20: Alexander Schrijver, A combinatorial algorithm minimizing submodular functions in strongly polynomial time, Journal of Combinatorial Theory Series B, v.80 n.2, p.346-355, Nov. 2000 [doi>10.1006/jctb.2000.1989]
• 21: A. Schrijver, Combinatorial Optimization; Polyhedra and Efficiency. Springer-Verlag, Berlin, 2003.
• 22: G. Wegner, Graphs with given diameter and a coloring problem. Technical Report, University of Dortmund, 1977.
• 23: S. A. Wong, Colouring graphs with respect to distance. M.Sc. Thesis, Department of Combinatorics and Optimization, University of Waterloo, 1996.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph labeling