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
    0 references
    0 references
    0 references
    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
    0 references
    circular coloring
    0 references
    edge-coloring
    0 references
    girth
    0 references
    Petersen graph
    0 references
    snark
    0 references
    0 references
    0 references
    0 references