Asymptotic Lower Bounds on Circular Chromatic Index of Snarks

  • Martin Mačaj
  • Ján Mazák
Keywords: snark, chromatic index, circular chromatic index, cubic graph

Abstract

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$.

Published
2013-04-09
Article Number
P2