Name
Abstract | ||
|---|---|---|
A facial parity edge colouring of a connected bridgeless plane graph is such an edge colouring in which no two face-adjacent edges receive the same colour and, in addition, for each face f and each colour c, either no edge or an odd number of edges incident with f is coloured with c. Let χp′(G) denote the minimum number of colours used in such a colouring of G. In this paper we prove that χp′(G)≤20 for any 2-edge-connected plane graph G. In the case when G is a 3-edge-connected plane graph the upper bound for this parameter is 12. For G being 4-edge-connected plane graph we have χp′(G)≤9. On the other hand we prove that some bridgeless plane graphs require at least 10 colours for such a colouring. |
Year | DOI | Venue |
|---|---|---|
2012 | 10.1016/j.disc.2012.03.036 | Discrete Mathematics |
Keywords | Field | DocType |
Plane graph,Facial walk,Edge colouring | Discrete mathematics,Combinatorics,Bound graph,Upper and lower bounds,Edge contraction,String graph,Dual graph,Petersen graph,Parity (mathematics),Planar graph,Mathematics | Journal |
Volume | Issue | ISSN |
312 | 17 | 0012-365X |
Citations | PageRank | References |
8 | 1.05 | 7 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Július Czap | 1 | 80 | 15.40 |
| Stanislav Jendrol' | 2 | 283 | 38.72 |
| František Kardoš | 3 | 87 | 9.72 |
| Roman Soták | 4 | 128 | 24.06 |