Name
Abstract | ||
|---|---|---|
Let G = ( V , E , F ) be a connected 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 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 ź { V ź E , E ź F } , and a facial list 8-colouring with respect to X = V ź E ź 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 ź { 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 ź F . |
Year | DOI | Venue |
|---|---|---|
2016 | 10.1016/j.disc.2016.05.034 | Discrete Mathematics |
Keywords | Field | DocType |
List colouring,Facial colouring,Total colouring,Entire colouring,Plane graph | Discrete mathematics,Graph,Combinatorics,Vertex (geometry),Planar graph,Mathematics | Journal |
Volume | Issue | ISSN |
339 | 11 | 0012-365X |
Citations | PageRank | References |
1 | 0.35 | 15 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Igor Fabrici | 1 | 101 | 14.64 |
| Stanislav Jendrol' | 2 | 283 | 38.72 |
| Margit Voigt | 3 | 314 | 39.78 |