Name
Abstract | ||
|---|---|---|
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. |
Year | DOI | Venue |
|---|---|---|
2016 | 10.1016/j.disc.2015.09.011 | Discrete Mathematics |
Keywords | Field | DocType |
Plane graph,Entire colouring,Facial colouring,Edge–face colouring | Graph,Discrete mathematics,Combinatorics,Vertex (geometry),Mathematics,Planar graph | Journal |
Volume | Issue | ISSN |
339 | 2 | 0012-365X |
Citations | PageRank | References |
1 | 0.36 | 16 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Igor Fabrici | 1 | 101 | 14.64 |
| Stanislav Jendrol' | 2 | 283 | 38.72 |
| Michaela Vrbjarová | 3 | 8 | 1.64 |