Edge and total choosability of near-outerplanar graphs

Article English OPEN
Hetherington, TJ ; Woodall, DR (2006)
  • Publisher: International Press

It is proved that, if G is a K4-minor-free graph with maximum degree ∆ ≥ 4, then G is totally (∆ + 1)-choosable; that is, if every element (vertex or edge) of G is assigned a list of ∆ + 1 colours, then every element can be coloured with a colour from its own list in such a way that every two adjacent or incident elements are coloured with different colours. Together with other known results, this shows that the List-Total-Colouring Conjecture, that ch’’(G) = χ’(G) for every graph G, is true for all K4-minor-free graphs. The List-Edge-Colouring Conjecture is also known to be true for these graphs. As a fairly straightforward consequence, it is proved that both conjectures hold also for all K2,3-minor free graphs and all ( K2 + (K1 U K2))-minor-free graphs.
  • References (13)
    13 references, page 1 of 2

    [1] O. V. Borodin, A. V. Kostochka and D. R. Woodall, List edge and list total colourings of multigraphs, J. Combin. Theory Ser. B 71 (1997), 184{204.

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

    [3] M. N. Ellingham and L. Goddyn, List edge colourings of some 1-factorable multigraphs, Combinatorica 16 (1996), 343{352.

    [4] P. Erdo}s, A. L. Rubin and H. Taylor, Choosability in graphs, in: Proc. West Coast Conference on Combinatorics, Graph Theory and Computing, Arcata, 1979, Congr. Numer. 26 (1980), 125{157.

    [5] A. J. W. Hilton and P. D. Johnson, The Hall number, the Hall index, and the total Hall number of a graph, Discrete Applied Math. 94 (1999), 227{245.

    [6] M. Juvan, B. Mohar and R. Skrekovski, List total colourings of graphs, Combin. Probab. Comput. 7 (1998), 181{188.

    [7] M. Juvan, B. Mohar and R. Thomas, List edge-colorings of series-parallel graphs, Electron. J. Combin. 6 (1999), #R42, 6pp.

    [8] A. V. Kostochka and D. R. Woodall, Choosability conjectures and multicircuits, Discrete Math. 240 (2001), 123{143.

    [9] W. Wang and K.-W. Lih, Choosability, edge choosability, and total choosability of outerplane graphs, European J. Combin 22 (2001), 71{78.

    [10] D. R. Woodall, A short proof of a theorem of Dirac's about Hadwiger's conjecture, J. Graph Theory 16 (1992), 79{80.

  • Metrics
    views in OpenAIRE
    views in local repository
    downloads in local repository

    The information is available from the following content providers:

    From Number Of Views Number Of Downloads
    Institutional Repository - IRUS-UK 0 6
Share - Bookmark