Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
10334295 | Theoretical Computer Science | 2005 | 9 Pages |
Abstract
A Fano colouring is a colouring of the edges of a cubic graph by points of the Fano plane such that the colours of any three mutually adjacent edges form a line of the Fano plane. It has recently been shown by Holroyd and Å koviera [Colouring of cubic graphs by Steiner triple systems, J. Combin. Theory Ser. B 91 (2004) 57-66] that a cubic graph has a Fano colouring if and only if it is bridgeless. In this paper we prove that six, and conjecture that four, lines of the Fano plane are sufficient to colour any bridgeless cubic graph. We establish connections of our conjecture to other conjectures concerning bridgeless cubic graphs, in particular to the well-known conjecture of Fulkerson about the existence of a double covering by 1-factors in every bridgeless cubic graph.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Edita MáÄajová, Martin Å koviera,