Asymptotic lower bounds on circular chromatic index of snarks (Q1953476)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Asymptotic lower bounds on circular chromatic index of snarks |
scientific article |
Statements
Asymptotic lower bounds on circular chromatic index of snarks (English)
0 references
7 June 2013
0 references
Summary: We prove that the circular chromatic index of a cubic graph \(G\) with \(2k\) vertices and chromatic index 4 is at least \(3+2/k\). This bound is (asymptotically) optimal for an infinite class of cubic graphs containing bridges. We also show that the constant 2 in the above bound can be increased for graphs with larger girth or higher connectivity. In particular, if \(G\) has girth at least 5, its circular chromatic index is at least \(3+2.5/k\). Our method gives an alternative proof that the circular chromatic index of the generalised type 1 Blanuša snark \(B_m^1\) is \(3+2/3m\).
0 references
snark
0 references
chromatic index
0 references
circular chromatic index
0 references
cubic graph
0 references