Entire choosability of near-outerplane graphs

Article English OPEN
Hetherington, Timothy J. (2009)
  • Publisher: Elsevier BV
  • Journal: Discrete Mathematics, volume 309, issue 8, pages 2,153-2,165 (issn: 0012-365X)
  • Related identifiers: doi: 10.1016/j.disc.2008.04.043
  • Subject: Theoretical Computer Science | Discrete Mathematics and Combinatorics

It is proved that if G is a plane embedding of a K4-minor-free graph with maximum degree Δ, then G is entirely 7-choosable if Δ≤4 and G is entirely (Δ+ 2)-choosable if Δ≥ 5; that is, if every vertex, edge and face of G is given a list of max{7,Δ+2} colours, then every element can be given a colour from its list such that no two adjacent or incident elements are given the same colour. It is proved also that this result holds if G is a plane embedding of a K2,3-minor-free graph or a (K2 + (K1 U K2))-minor-free graph. As a special case this proves that the Entire Colouring Conjecture, that a plane graph is entirely (Δ + 4)-colourable, holds if G is a plane embedding of a K4-minor-free graph, a K2,3-minor-free graph or a (K2 + (K1 U K2))-minor-free graph.
  • References (16)
    16 references, page 1 of 2

    [1] O. V. Borodin and D. R. Woodall, Thirteen colouring numbers for outerplane graphs, Bull. Inst. Combin. Appl. 14 (1995), 87-100.

    [2] O. V. Borodin, Solution of Ringel's problem on vertex-face colouring of plane graphs and colouring of 1-planar graphs (in Russian), Metody Diskret. Analiz. 41 (1984), 12-26.

    [3] G. A. Dirac, A property of 4-chromatic graphs and some remarks on critical graphs, J. London Math. Soc. 27 (1952), 85-92.

    [4] P. Erd˝os, A. L. Rubin and H. Taylor, Choosability in graphs, Proc. West Coast Conference on Combinatorics, Graph Theory and Computing, Arcata, 1979, Congr. Numer. 26 (1980), 125-157.

    [5] T. J. Hetherington, List-colourings of near-outerplanar graphs, PhD Thesis, University of Nottingham, 2006.

    [6] T. J. Hetherington, Coupled choosability of near-outerplane graphs, submitted February 2007.

    [7] T. J. Hetherington, Edge-face choosability of near-outerplane graphs, submitted February 2007.

    [8] T. J. Hetherington and D. R. Woodall, Edge and total choosability of nearouterplanar graphs, Electr. J. Combin. 13 (2006), #R98, 7pp.

    [9] H. V. Kronk and J. Mitchem, The entire chromatic number of a normal graph is at most seven, Bull. Amer. Math. Soc. 78 (1972), 799-800.

    [10] H. V. Kronk and J. Mitchem, A seven-colour theorem on the sphere, Discrete Math. 5 (1973), 253-260.

  • Metrics
    No metrics available
Share - Bookmark