Facial parity edge colouring

Abstract : A facial parity edge colouring of a connected bridgeless plane graph is an edge colouring in which no two face-adjacent edges (consecutive edges of a facial walk of some face) receive the same colour, in addition, for each face α and each colour c, either no edge or an odd number of edges incident with α is coloured with c. From Vizing's theorem it follows that every 3-connected plane graph has a such colouring with at most Δ* + 1 colours, where Δ* is the size of the largest face. In this paper we prove that any connected bridgeless plane graph has a facial parity edge colouring with at most 92 colours.
Document type :
Journal articles
Complete list of metadatas

Cited literature [6 references]  Display  Hide  Download

https://hal.inria.fr/inria-00634947
Contributor : František Kardoš <>
Submitted on : Wednesday, November 9, 2011 - 1:53:29 PM
Last modification on : Tuesday, December 18, 2018 - 4:38:30 PM
Long-term archiving on : Friday, February 10, 2012 - 2:21:16 AM

File

CJK11.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : inria-00634947, version 1

Collections

Citation

Július Czap, Stanislav Jendrol', František Kardoš. Facial parity edge colouring. Ars Mathematica Contemporanea, DMFA Slovenije, 2011, 4 (2), pp.255-269. ⟨http://amc.imfm.si/index.php/amc/article/view/129⟩. ⟨inria-00634947⟩

Share

Metrics

Record views

295

Files downloads

388