Facial list colourings of plane graphs Wissenschaftlicher Artikel uri icon

Open Access

  • false

Peer Reviewed

  • true

Abstract

  • Let G = (V, E, F) be a connected plane graph, with vertex set V, edge set E, and face set F. For X is an element of {V, E,F,V boolean OR E,V boolean OR F,E boolean OR E,V boolean OR E boolean OR F}, two distinct elements of X are facially adjacent in G if they are incident elements, adjacent vertices, adjacent faces, or facially adjacent edges (edges that are consecutive on the boundary walk of a face of G). A list k-colouring is facial with respect to X if there is a list k-colouring of elements of X such that facially adjacent elements of X receive different colours. We prove that every plane graph G = (V, E, F) has a facial list 4-colouring with respect to X = E, a facial list 6-colouring with respect to X is an element of {V boolean OR E, E boolean OR F}, and a facial list 8-colouring with respect to X = V boolean OR E boolean OR F. For plane triangulations, each of these results is improved by one and it is tight. These results complete the theorem of Thomassen that every plane graph has a (facial) list 5-colouring with respect to X is an element of {V, F} and the theorem of Wang and Lih that every simple plane graph has a (facial) list 7-colouring with respect to X = V boolean OR F. (C) 2016 Elsevier B.V. All rights reserved.

Veröffentlichungszeitpunkt

  • Juni 11, 2016