Asymptotic lower bounds on circular chromatic index of snarks

作者：Macaj Martin^*; Mazak Jan

来源：Electronic Journal of Combinatorics, 2013, 20(2): P2.

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 Blanusa snark B-m(1) is 3 + 2/3m.

• 出版日期2013-4-9