Facial entire colouring of plane graphs

• Published in: Discrete mathematics 2016-02, Vol.339 (2), p.626-631
• Main Authors: Fabrici, I., Jendrol’, S., Vrbjarová, M.
• Format: Article
• Language: English
• Subjects: Edge–face colouring; Entire colouring; Facial colouring; Plane graph
• ISSN: 0012-365X; 1872-681X
• DOI: 10.1016/j.disc.2015.09.011

Let G=(V,E,F) be a connected, loopless, and bridgeless plane graph, with vertex set V, edge set E, and face set F. For X∈{V,E,F,V∪E,V∪F,E∪F,V∪E∪F}, two elements x and y of X are facially adjacent in G if they are incident, or they are adjacent vertices, or adjacent faces, or facially adjacent edges (i.e. edges that are consecutive on the boundary walk of a face of G). A k-colouring is facial with respect to X if there is a k-colouring of elements of X such that facially adjacent elements of X receive different colours. We prove that: (i) Every plane graph G=(V,E,F) has a facial 8-colouring with respect to X=V∪E∪F (i.e. a facial entire 8-colouring). Moreover, there is plane graph requiring at least 7 colours in any such colouring. (ii) Every plane graph G=(V,E,F) has a facial 6-colouring with respect to X=E∪F, in other words, a facial edge–face 6-colouring.