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$.
@article{10_37236_2388,
author = {Martin Ma\v{c}aj and J\'an Maz\'ak},
title = {Asymptotic lower bounds on circular chromatic index of snarks},
journal = {The electronic journal of combinatorics},
year = {2013},
volume = {20},
number = {2},
doi = {10.37236/2388},
zbl = {1266.05038},
url = {http://geodesic.mathdoc.fr/articles/10.37236/2388/}
}
TY - JOUR
AU - Martin Mačaj
AU - Ján Mazák
TI - Asymptotic lower bounds on circular chromatic index of snarks
JO - The electronic journal of combinatorics
PY - 2013
VL - 20
IS - 2
UR - http://geodesic.mathdoc.fr/articles/10.37236/2388/
DO - 10.37236/2388
ID - 10_37236_2388
ER -
%0 Journal Article
%A Martin Mačaj
%A Ján Mazák
%T Asymptotic lower bounds on circular chromatic index of snarks
%J The electronic journal of combinatorics
%D 2013
%V 20
%N 2
%U http://geodesic.mathdoc.fr/articles/10.37236/2388/
%R 10.37236/2388
%F 10_37236_2388
Martin Mačaj; Ján Mazák. Asymptotic lower bounds on circular chromatic index of snarks. The electronic journal of combinatorics, Tome 20 (2013) no. 2. doi: 10.37236/2388
