Circular edge-colorings of cubic graphs with girth six (Q5900963)
From MaRDI portal
scientific article; zbMATH DE number 5716642
Language | Label | Description | Also known as |
---|---|---|---|
English | Circular edge-colorings of cubic graphs with girth six |
scientific article; zbMATH DE number 5716642 |
Statements
Circular edge-colorings of cubic graphs with girth six (English)
0 references
3 June 2010
0 references
A \textit{\((p,q)\)-edge-coloring} of a graph \(G\) is a coloring of the edges with \(\{1,\dots,p\}\) such that any two adjacent edges receive colors \(a,b\) with \(q \leq |a-b| \leq p-q\). The \textit{circular chromatic index} is the infimum \(p/q\) such that \(G\) has a \((p,q)\)-edge-coloring. This is a fractional relaxation of the chromatic index. Bridgeless cubic graphs are especially interesting since those of chromatic number 4 (\textit{snarks}) contain possible counterexamples to several important conjectures. It is known that the Petersen graph has circular chromatic number 11/3, and it is conjectured that this is the only bridgeless cubic graph with circular chromatic number at least 11/3. In this paper the authors show that the circular chromatic index of any (sub)cubic graph with odd girth at least 7 is at most 7/2.
0 references
circular coloring
0 references
edge-coloring
0 references
girth
0 references
Petersen graph
0 references
snark
0 references