Skip to Main content Skip to Navigation
New interface
Journal articles

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 metadata

Cited literature [6 references]  Display  Hide  Download
Contributor : František Kardoš Connect in order to contact the contributor
Submitted on : Wednesday, November 9, 2011 - 1:53:29 PM
Last modification on : Thursday, August 4, 2022 - 4:52:40 PM
Long-term archiving on: : Friday, February 10, 2012 - 2:21:16 AM


Files produced by the author(s)


  • HAL Id : inria-00634947, version 1



Július Czap, Stanislav Jendrol', František Kardoš. Facial parity edge colouring. Ars Mathematica Contemporanea, 2011, 4 (2), pp.255-269. ⟨inria-00634947⟩



Record views


Files downloads