\documentclass[12pt]{article}
\usepackage{e-jc}
\specs{P2}{20(2)}{2013}

% we recommend these ams packages
\usepackage{amsthm,amsmath,amssymb}

% we recommend the graphicx package for importing figures
\usepackage{graphicx}
%\usepackage[T1]{fontenc}

% use this command to create hyperlinks (optional and recommended)
\usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref}

% use these commands for typesetting doi and arXiv references in the bibliography
\newcommand{\doi}[1]{\href{http://dx.doi.org/#1}{\texttt{doi:#1}}}
\newcommand{\arxiv}[1]{\href{http://arxiv.org/abs/#1}{\texttt{arXiv:#1}}}

% declare theorem-like environments
\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{fact}[theorem]{Fact}
\newtheorem{observation}[theorem]{Observation}
\newtheorem{claim}[theorem]{Claim}

\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{open}[theorem]{Open Problem}
\newtheorem{problem}[theorem]{Problem}
\newtheorem{question}[theorem]{Question}

\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{note}[theorem]{Note}


\let\eps\varepsilon
\let\phi\varphi
\def\Z{{\mathbb Z}}


\def\Alpha{A}
\def\Beta{B}
\def\Rho{R}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\title{\bf Asymptotic lower bounds on\\ circular chromatic index of snarks}
\author{
Martin Mačaj\\
\small Comenius University\\[-0.8ex] 
\small Mlynská dolina, 842 48 Bratislava, Slovakia\\
\small\tt martin.macaj@fmph.uniba.sk\\
\and
Ján Mazák\\
\small Trnava University\\[-0.8ex]
\small Priemyselná 4, 918 43 Trnava, Slovakia\\
\small\tt jan.mazak@truni.sk
}

\date{\dateline{May 25, 2012}{Mar 28, 2013}{Apr 9, 2013}\\
\small Mathematics Subject Classifications: 05C15}

\begin{document}

\maketitle

\begin{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$.
\end{abstract}

\section{Introduction}

Circular colourings have become an active research area in the last decade. Meanwhile, various interesting connections between circular colourings and other areas of graph theory and theoretical computer science have been revealed: circular colourings can be equivalently defined via graph homomorphisms, balanced orientations, or tensions; circular chromatic number is dual to a certain invariant studied for periodic scheduling problems. More on this can be found in the surveys \cite{zhu1} and \cite{zhu2}. 

This article focuses on circular edge-colourings of cubic graphs. Basic properties of circular edge-colorings are covered in Section \ref{cec}; in this section we also introduce our new approach for determining a lower bound on circular chromatic index. The essence of this approach is captured in Proposition \ref{counting}.

Cubic graphs constitute one of the most important classes of graphs because various important conjectures such as the Cycle Double Cover Conjecture and the Tutte's $5$-flow conjecture have been reduced to graphs with maximum degree $3$. It transpired that many conjectures hold trivially for cubic graphs that have a $3$-edge-colouring, hence the difficulty consists in proving them for cubic graphs with chromatic index $4$. We call such uncolourable graphs {\it snarks\/}
(for our purpose, they may contain bridges). 

The aim of this article is to establish a lower bound on the circular chromatic index of a snark depending on its order. An outline of previous results concerning circular chromatic index of snarks is given in Section \ref{cchi} and the established bounds are presented in Sections \ref{s1}, \ref{girthFive}, and \ref{improvement}. The most important of the bounds is the following: if $G$ is a snark with $2k$ vertices and girth at least $5$, then the circular chromatic index of $G$ is at least
$$
3+{2.5\over k}.
$$
If we further assume that $G$ does not contain a special subgraph (see Lemma~\ref{ll1} for the details), the bound improves to $3+2.\overline{6}/k$.
The better bound leads to a completely new way of proving that the generalised type 1 Blanu\v sa snark with $2k$ vertices has circular chromatic index $3+2.\overline{6}/k$, as established in \cite{m}. The advantage of our proof is that we avoid tedious and long case analysis that is essential in the original proof. 

\section{Circular edge-colourings}
\label{cec}

A \emph{circular $r$-edge-colouring} of a graph $G$ is an assignment $c$ of colours, that is, real numbers from the interval $[0,r)$, to the edges of $G$ in such a way that for any pair of adjacent edges $e$ and $f$ we have $1\le |c(e)-c(f)|\le r-1$. The \emph{circular chromatic index} of a graph $G$, denoted by $\chi_c'(G)$, is the infimum of all $r$ such that $G$ admits a circular $r$-edge-colouring. In fact, the infimum can be replaced by minimum \cite{zhu1}. One can easily check that any ``usual'' edge-colouring of a graph (with colours being integers from the set $\{0,1,\dots,r-1\}$) is also a circular edge-colouring, hence the circular chromatic index is a natural refinement of the chromatic index. Precisely, $\chi(G)=\left\lceil\chi_c'(G)\right\rceil$; a proof of this and many other basic properties of circular colourings used in this paper can be found in \cite{zhu1}.

The problem of determining if a given rational number is the circular chromatic index of a given graph is known to be NP-hard \cite{zhu1}. In practice, it is tough even for cubic graphs on $30$ vertices. As a consequence, there are only a few classes of graphs with known circular chromatic index (see \cite{zhu2} for some details).

When attempting to determine the circular chromatic index of a particular graph $G$, one naturally starts with some general bounds that restrict the set of possible values of $\chi_c'(G)$. Obviously, to find an upper bound for $\chi_c'(G)$ we just need to find a circular edge-colouring of $G$. However, to establish a lower bound $\chi_c'(G)\ge r$, one needs to prove that there is no circular $r'$-edge-colouring for any $r'<r$, and at present we have no efficient methods for this problem (neither theoretical nor computational, see \cite{gheblehova dizertacka}). Here a decent lower bound might be useful. Such a bound on circular flow number has been given in \cite{rele} in terms of the order of the graph; we will also follow this approach. (For more details on the relationship between circular flows and circular colourings we refer the reader to the articles \cite{gtz, panzhu}.)

Let $G$ be a graph with maximum degree $\Delta$ and chromatic index $\Delta+1$. Then
\begin{equation}
\label{bound1}
\chi_c'(G)\ge \Delta + {2\over |V(G)|}.
\end{equation}
This bound is based on a lemma from \cite{zhu1}: if $p$ and $q$ are two coprime integers and $\chi'_c(G)=p/q$ for a graph $G$ with chromatic index $\Delta(G)+1$, then the denominator $q$ does not exceed $|V(G)|/2$. In fact, the denominator cannot exceed the size of the largest matching in $G$ (see \cite[Theorem 3]{hk}).

The bound given above is trivial and is of no practical use. Fortunately, it is possible to exploit the structure of matchings in a graph and to derive a better bound. As we will show later, some further improvements are possible for graphs with larger girth or larger cyclic edge-connectivity.

The concept of circular colouring was introduced by Vince in \cite{vince}. The definition used by Vince is a bit different from the above-given definition, but they are equivalent (see \cite{zhu1} for a proof). Since Vince's definition is rather useful for our work, we present it here. A $(p,q)$-edge-colouring of a graph $G$ is an assignment $c$ of colours, that is, integers from the set $\{0,1,2,\dots,p-1\}$, to the edges of $G$ in such a way that for any pair of adjacent edges $e$ and $f$ we have $q\le |c(e)-c(f)|\le p-q$. The circular chromatic index is the infimum of all fractions $p/q$ such that $G$ admits a $(p,q)$-edge-colouring. 

The set of colours of a $(p,q)$-edge-colouring is $\{1,2,\dots,p\}$, with colours taken modulo $p$.
A set of $r$ consecutive colours will be called a {\it segment\/} of length $r$. For example, the set $\{p-1, p, 1, 2\}$ is a segment of length $4$. We say that a segment colours $m$ edges if there are exactly $m$ edges coloured by the colours constituting the segment. By the subgraph of a graph $G$ induced by a set of edges $S\subseteq E(G)$ we mean the subgraph of $G$ induced by all endvertices of the edges in $S$.
The main idea of our approach is captured in the following simple proposition.

\begin{proposition}
\label{counting}
Let $G$ be a cubic graph with $2k$ vertices, chromatic index $4$ and a $(3v+u,v)$-edge-colouring.
Let $t$ and $m$ be positive integers.
If any segment of length $tu$ colours at least $m$ edges, then
$$
{u\over v}\ge {3m\over 3tk-m}.
$$
Therefore, $\chi_c'(G) > 3+m/tk$.
\end{proposition}

\begin{proof}
Each colour belongs to $tu$ segments of length $tu$. Since $G$ has $3k$ edges and there are $3v+u$ different segments of length $tu$, the average number of edges coloured by such a segment is
$$
{3k\cdot tu\over 3v+u}.
$$
The average value is at least as big as the minimal value, which is at least $m$ in our situation.
A simple manipulation of this inequality gives the desired lower bound for the fraction $u/v$ and, consequently, for $\chi_c'(G)$.
\end{proof}

\begin{remark}
\label{rem1}
Note that the segments in Proposition~\ref{counting} need not to be contiguous: we can replace them by sets of colours of size $tu$ such that each colour appears in $tu$ of them.
\end{remark}

Proposition \ref{counting} reduces the problem of proving the lower bound to proving that a segment of a given length colours sufficiently many edges. The latter problem is easier to approach. For instance, Lemma~\ref{u2} shows that a segment of length $u$ colours at least two edges, and then Proposition \ref{counting} with $t = 1$ and $m = 2$ yields the lower bound $3+2/k$.
Although we focus on cubic graphs in this article, our methods can be generalised to graphs of larger maximum degree in a straightforward way; see \cite{barborka} for an example. 


\section{Circular chromatic index of cubic graphs}
\label{cchi}

The circular chromatic index provides a measure that can be used to say ``how far'' a cubic graph is from being $3$-edge-colourable. All $3$-edge-colourable cubic graphs have circular chromatic index $3$, thus they are not exciting at all from our point of view. We are interested in {\it snarks\/}, connected cubic graphs with chromatic index $4$. Usually it is required that a snark is bridgeless, that is, $2$-edge-connected, but we will keep the definition as broad as possible. We allow our graphs to have multiple edges but exclude graphs with loops. More about snarks and their history can be found in the survey \cite{watkins1}; the article \cite{ns} is devoted to a discussion of various aspects of triviality of snarks. The most common requirements imposed on a non-trivial snark are girth at least $5$ and cyclic edge-connectivity at least $4$.

The circular chromatic index of a snark lies in the set $(3, 11/3]\cup \{4\}$. The upper bound of $11/3$ for bridgeless snarks was proved by Afshani et al. \cite{agghtz}. The values of circular chromatic index have been determined for Isaac snarks \cite{flower}, Goldberg snarks \cite{goldbergove}, a few classes of graphs that are trivial in some sense (for instance, see \cite{nadolski}), generalised Blanu\v sa snarks \cite{m, blanusa2}, and the cubic graphs that have been constructed to show that any rational number from the interval $(3,10/3)$ is equal to the circular chromatic index of some cubic graph \cite{konstrukcia}.

An improvement of the lower bound \eqref{bound1} on circular chromatic index of snarks was established in \cite{diplomovka}: a snark on $2k$ vertices has circular chromatic index at least
\begin{equation}
\label{bound2}
3+{2\over k}.
\end{equation}
In this article, we focus on lower bounds in the form $\chi_c'(G)\ge 3+c/k$, where $k=|V(G)|/2$ and $c$ is a constant. It is often true that such a bound holds for all but finitely many snarks, hence we will adopt an asymptotical approach described later.

The proof of the bound \eqref{bound2} and also our subsequent proofs are based on the following observation: a cubic graph is $3$-edge-colourable if and only if it has two disjoint perfect matchings ($1$-factors). Hence a cubic graph is a snark if and only if it does not have two disjoint $1$-factors. This does not exclude graphs with bridges, and parallel edges are also naturally included in this equivalent definition of a snark.

In Section \ref{s1} we prove a slight improvement of the bound \eqref{bound2} and show that it is tight for an infinite class of graphs with girth $2$ and cyclic edge-connectivity $1$. If we want to improve the bound further, we have to restrict ourselves to a subclass of the class of snarks, for instance, we can assume larger girth or larger cyclic edge-connectivity. As we will see in Sections \ref{girthFive} and \ref{improvement}, both these ways allow us to improve the bound. In our proofs we need some auxiliary technical results; we have grouped them in an appendix to avoid disrupting the exposition.

\section{A lower bound for snarks of given order}
\label{s1}

We will usually write the value of the circular chromatic index of a snark in the form $3+u/v$, where $u$ and $v$ are coprime positive integers. Since all cubic graphs are $4$-edge-colourable, we assume $u\le v$. There exist snarks with circular chromatic index $4$; they were completely characterised by Afshani et~al.~in \cite{agghtz}.
Since we are working on the lower bound, snarks with circular chromatic index $4$ are of no interest to us and we will assume $u < v$ throughout the article.

The following theorem gives a lower bound slightly better than the bound \eqref{bound2}.

\begin{theorem}
\label{b2}
Let $G$ be a snark on $2k$ vertices. Then
$$
\chi'_c(G) \ge 3+{2\over k-1}.
$$
This bound is tight for any odd $k\ge 3$.
\end{theorem}

The proof of Theorem~\ref{b2} consists of three parts. First, we prove that a segment of length $u$ colours at least two edges and obtain a lower bound on $\chi_c'(G)$ from Proposition~\ref{counting}. Then we improve the obtained bound using a number-theoretic argument (Lemma~\ref{l1}). Finally, we construct a class of graphs for which the improved lower bound is attained.

\begin{lemma}
\label{u2}
Let $G$ be a snark with $2k$ vertices. In any $(3v+u,v)$-edge-colouring of $G$,
every segment of length $u$ colours at least two edges.
\end{lemma}

\begin{proof}
Consider a segment of length $u$. We divide the remaining $3v$ colours into three consecutive segments of length $v$. The edges coloured by any of these three segments form a matching. If two of the matchings created in this way are perfect, we have two disjoint $1$-factors, contradictory to the assumption that $G$ is a snark. Hence at most one of these matchings has $k$ edges and the remaining two have at most $k-1$ edges. Together there are at most $k+2(k-1)=3k-2$ edges coloured by the $3v$ colours. Since $G$ is cubic, it has $3k$ edges; therefore, our segment of length $u$ colours at least two edges.
\end{proof}

\begin{proof}[Proof of Theorem~\ref{b2}.]
Let $G$ be a snark on $2k$ vertices with circular chromatic index $3+u/v$. Since the infimum in the definition of circular chromatic index is attained, there exist a $(3v+u,v)$-edge-colouring of $G$. According to Lemma~\ref{u2}, any segment of length $u$ colours at least two edges. By using Proposition \ref{counting} for $t=1$ and $m=2$, we obtain that
\begin{equation}
\label{somebound}
{u\over v}\ge {2\over k-{2\over 3}}.
\end{equation}

One of the basic properties proved in \cite{zhu1} asserts that if a snark on $2k$ vertices has circular chromatic index $p/q$ with $p$ and $q$ coprime, then there exist a $(p,q)$-edge-colouring of this snark and for any such $(p,q)$-edge-colouring we have $p\le 3k$ and $q\le k$. Hence we are interested only in fractions $p/q$ with $q\le k$.
Moreover, note that the smallest snark (according to our definition) has $6$ vertices, hence the assumption $k>2$ in Lemma~\ref{l1} is always satisfied.
Lemma~\ref{l1} put together with the inequality \eqref{somebound} gives the lower bound of Theorem~\ref{b2}. It remains to prove that this bound is tight.

We construct a class of graphs $\{H_m\}_{m=1}^\infty$; the bound is tight for any graph in this class. Let $H'_m$ be a graph composed of two copies of the cycle $C_{m+1}$ with one vertex of the first copy joined to a vertex of the second copy. The graph $H_m$ is constructed from $H_m'$ by replacing each vertex of degree two in $H_m'$ by a digon (two vertices joined by a pair of parallel edges).

The graph $H_m$ with $4m+2$ vertices has $k=2m+1$. To complete the proof of Theorem~\ref{b2}, we need to find a $(3k-1,k-1)$-edge-colouring of the graph $H_m$. An equivalent $(3m+1, m)$-edge-colouring of $H_m$ is given in Fig. \ref{Hmcol}. The edges not included in the digons are subsequently coloured by the colours $0, 1, 2, 3, \dots, m$ along the circle---every digon allows us to shift the colour by $1$.
\end{proof}

\begin{figure}
\begin{center}
\includegraphics[scale=0.95]{v20i2p2/obr-1}
\end{center}
\caption{A $(3m+1,m)$-edge-colouring of the graph $H_m$.}
\label{Hmcol}
\end{figure}

The bound \eqref{bound2} is a consequence of Lemma~\ref{u2} and Proposition \ref{counting} that does not depend on Lemma~\ref{l1} which is of number-theoretic nature and reveals almost nothing about the structure of edge-colourings of snarks. Moreover, the improvement achieved by using Lemma~\ref{l1} is a minor one and is totally negligible from the asymptotic point of view which we will adopt in Section~\ref{improvement}. Nevertheless, Lemma~\ref{l1} is included here to illustrate that the asymptotic bounds obtained in this paper can be improved to exact bounds (with some more or less tedious effort).

Both the bounds \eqref{bound1} and \eqref{bound2} are of the form $3+b/k$, where $b$ is a constant.
It is natural to ask for the bound with the largest possible constant $b$. A consequence of Theorem~\ref{b2} is that the largest possible such constant is $b=2$.
However, since the bound is tight for snarks with girth $2$ and cyclic edge-connectivity $1$ which are usually considered trivial, it is reasonable to expect that the bound of Theorem~\ref{b2} can be improved for non-trivial snarks with girth at least $5$. We show one such improvement in the following section.

\section{A lower bound for snarks of girth at least five}
\label{girthFive}

We start this section by showing why the assumption of larger girth is useful. Consider two different $1$-factors of a snark. In how many edges must these $1$-factors differ? If we exclude snarks with parallel edges, the $1$-factors must differ in at least two edges. If we assume that the girth of our snark is at least five, then the $1$-factors must differ in at least three edges.
We can use this observation to improve the lower bound for graphs of girth at least $5$.

\begin{lemma}
\label{2u5}
Let $G$ be a snark with $2k$ vertices and with girth at least $5$.
In any $(3v+u,v)$-edge-colouring of $G$,
every segment of length $2u$ colours at least five edges and
$$
{u\over v}\ge {15\over 6k-5} = {2.5\over k-{5\over 6}}.
$$
\end{lemma}

\begin{proof}
We know that any two disjoint segments of length $v$ colour together at most $2k-1$ edges, otherwise we would have two disjoint $1$-factors.

First, we prove that any segment of length $v-u$ colours at most $k-3$ edges.
Assume that there is a segment of length $v-u$ constituted by colours, say, $1,\dots,v-u$, which colours $k-2$ edges. Since any segment of length $u$ colours at least two edges (Lemma~\ref{u2}), the edges coloured by the colours \hbox{$3v+1, 3v+2,\dots, 3v+u,1,\dots,v-u$} form a perfect matching and there are exactly two edges coloured by the colours $3v+1,\dots,3v+u$. Similarly, the edges coloured by the colours $1,\dots,v$ form a perfect matching and there are exactly two edges coloured by the colours $v-u+1,\dots,v$. Thus there are two $1$-factors in $G$ that differ in only two edges, contradicting the assumption that $G$ has girth at least $5$.

Assume now that a segment of length $2u$ colours at most four edges. This segment can be split into two neighbouring segments of length $u$, each of them colouring precisely two edges. Let these two segments be, say, $3v,3v+1,\dots,3v+u-1$ and $3v+u, 1, 2,\dots,u-1$.

The remaining $3v-u$ colours colour $3k-4$ edges.
There are three ways how to split $3v-u$ consecutive colours into two segments of length $v$ and one segment of length $v-u$.
We have proved that a segment of length $v-u$ colours at most $k-3$ edges, hence the remaining $2k-1$ edges are coloured by the two segments of length $v$, and this is possible only if one of them colours $k$ edges and the other one colours $k-1$ edges. The three possible ways of splitting the $3v-u$ colours into segments are summarized in the following tables telling how many edges are coloured by a particular segment. Because of the symmetry we may assume that the segment $u,\dots,v+u-1$ colours $k$ edges and the segment $2v,\dots,3v-1$ colours $k-1$ edges.
\begin{center}$
\begin{array}{|c|c|c|c|}\hline
\hbox{colours} & u,\dots,v+u-1& v+u,\dots,2v-1 & 2v,\dots,3v-1 \\ \hline \hbox{edges} & k & k-3 & k-1
\\ \hline\end{array}$
\end{center}
\begin{center}$
\begin{array}{|c|c|c|c|}\hline
\hbox{colours} & u,\dots,v+u-1& v+u,\dots,2v+u-1 & 2v+u,\dots,3v-1 \\ \hline \hbox{edges} & k & k-1 & k-3
\\ \hline\end{array}$
\end{center}
\begin{center}$
\begin{array}{|c|c|c|c|}\hline
\hbox{colours} & u,\dots,v-1& v,\dots,2v-1 & 2v,\dots, 3v-1 \\ \hline \hbox{edges} & k-3 & k & k-1
\\ \hline\end{array}$
\end{center}
By putting it all together, we obtain
\begin{center}$
\begin{array}{|c|c|c|c|}\hline
\hbox{colours} & 3v,\dots, 3v+u-1 & 3v+u,1, \dots, u-1  & u,\dots,v-1
 \\ \hline
\hbox{edges} & 2 & 2 &  k-3
 \\
\hline \hbox{colours} & v,\dots, v+u-1 & v+u,\dots,2v-1 & 2v, \dots, 2v+u-1\\
\hline
\hbox{edges} & 3 & k-3 & 2\\
\hline
\hbox{colours} &2v+u, \dots, 3v-1 & &\\
\hline
\hbox{edges}& k-3 & &\\
\hline\end{array}$
\end{center}

The edges coloured by the colours $u, \dots, v+u-1$ form a perfect matching $A$ and
the edges coloured by $v,\dots,2v-1$ form another perfect matching $B$. Therefore,
every edge of $G$ is on each end incident with some edge from $A$ and some edge from $B$.

In particular, each edge coloured by one of the colours $3v+u,1,2,\dots, u-1$ is on each
end incident with some edge coloured by a colour from $v,\dots,v+u-1$
(recall that the colours of two adjacent edges differ by at least $v$).
Similarly, each edge coloured by one of the colours $2v, \dots, 2v+u-1$ is on
each end incident with some edge coloured by a colour from $v,\dots,v+u-1$.
Let $H$ be the subgraph of $G$ induced by the seven edges coloured by colours
$3v+u,1,2,\dots,u-1, v, v+1, \dots,v+u-1, 2v, 2v+1\dots,2v+ u-1$.
Each vertex of $H$ is incident to one of the three edges coloured by the segment $v, v+1,\dots, v+u-1$; thus $H$ has
exactly six vertices. Since $\Delta(H)\le 3$ and $H$ has seven edges, it is easy to see that $H$ contains a cycle of length at most four,
and this contradicts the assumption on the girth of $G$.
Hence any segment of length $2u$ colours at least five edges.

The desired inequality then follows from Proposition \ref{counting} with $t=2$ and $m=5$.
\end{proof}

\begin{theorem}
\label{b2.5}
Let $G$ be a snark on $2k$ vertices with girth at least $5$. Then
$$
\chi'_c(G) > 3+{2.5\over k}.
$$
\end{theorem}

The restriction on girth allowed us to improve the lower bound on circular chromatic index. In the next section, we improve the lower bound even more.

\section{Snarks with larger girth or higher connectivity}
\label{improvement}

Before showing that higher cyclic connectivity leads to an improved lower bound, we give a general formulation of our problem.

\begin{problem}
What is the largest constant $b(g, \lambda_c)$ such that the inequality
$$
\chi'_c(G)\ge 3+{b(g, \lambda_c)\over k}
\postdisplaypenalty 500
$$
holds for all but finitely many snarks $G$ with $2k$ vertices, girth at least $g$ and cyclic edge-connectivity at least $\lambda_c$?
\end{problem}

The results that have been proven so far can be summed up as $b(2,1)=2$ and $b(5,\lambda_c)\ge 2.5$ for any $\lambda_c$.
The class of generalised type 1 Blanu\v sa snarks contains a snark on $8m+2$ vertices with circular chromatic index $3+2/3m$ for every positive integer $m$ (see \cite{m} for the proof).
This shows that $b(5,4)\le 8/3 = 2.\overline{6}$. Despite our effort we have not found any snark which would give a better upper bound on the constant $b(5,4)$.
We conjecture that $b(5,4) = 2.\overline{6}$. This conjecture is supported by the following two theorems.

\begin{theorem}
\label{boundgirth}
Let $G$ be a bridgeless snark on $2k$ vertices with girth at least $7$. Then
$$
\displaystyle \chi_c'(G) > 3+{2.\overline{6}\over k}.
$$
\end{theorem}

\begin{theorem}
\label{boundlambda}
Let $G$ be a cyclically $5$-edge-connected snark on $2k$ vertices ($k\ge 8$). Then 
$$
\displaystyle \chi_c'(G) > 3+{2.\overline{6}\over k}.
$$
\end{theorem}

Since a cubic graph with girth at least $7$ has more then $16$ vertices,
Theorem~\ref{boundgirth} is an immediate consequence of Lemma~\ref{ll1} and Proposition \ref{counting} for $t=3$ and $m=8$.
Lemma~\ref{ll1} with Proposition \ref{counting} also implies Theorem~\ref{boundlambda} because a cyclically $5$-edge-connected snark $G$ has girth at least $5$. In fact, the assumption $k\ge 8$ in Theorem~\ref{boundlambda} can be also left out since the only cyclically $5$-edge-connected snark with at most $16$ vertices is the Petersen graph with $10$ vertices and circular chromatic index $11/3$.

\begin{lemma}
\label{ll1}
Let $G$ be a bridgeless snark with $2k$ vertices ($k\ge 8$) and with girth at least $5$. Then at least one of the following statements is true:
\begin{itemize}
\item
In any $(3v+u,v)$-edge-colouring of $G$ such that $u/v < 1/2$,
every segment of length $3u$ colours at least $8$ edges;
\item
$G$ has a cycle-separating edge-cut of size at most $4$ with one
component $H$ of size $12$ and girth at most $6$;
\item
$G$ has a cycle-separating edge-cut of size at most $4$ with one
Hamiltonian component $H$ of size $10$ and girth at most $5$.
\end{itemize}
\end{lemma}

\begin{proof}
Let $G$ have a $(3v+u, v)$-edge-colouring with $u/v < 1/2$.
We prove that if a segment of length $3u$ colours at most $7$ edges, then $G$ contains a cycle of length at most $10$ and an edge-cut of size at most $4$ such that this edge-cut separates at least two components with cycles.

If $3u$ consecutive colours colour $7$ edges, we can divide the $3u$ colours into three consecutive segments $d_1$, $d_2$, and $d_3$ of length $u$. As a consequence of Lemmas \ref{u2} and \ref{2u5}, these segments colour two, three, and two edges respectively. Without a loss of generality we may assume that
\begin{eqnarray*}
d_1=\{1,2,\dots,u\},\quad d_2=\{u+1,u+2\dots,2u\},\quad d_3=\{2u+1,2u+2,\dots,3u\}.
\end{eqnarray*}
Let
\begin{eqnarray*}
& & a = \{3u+1,3u+2,\dots,v+u\},\\
& & x=\{ v+u+1,v+u+2,\dots,v+3u\},\\
& & b=\{v+3u+1, v+3u+2,\dots, 2v+u\},\\
& & y = \{2v+u+1, 2v+u+2, \dots, 2v+3u\},\\
& & c=\{2v+3u+1,2v+3u+2,\dots,3v+u\}.
\end{eqnarray*}
The segments $a$, $b$, $c$ have length $v-2u$; the segments $x$ and $y$ have length $2u$.
The sets of edges coloured by the segments $a$, $b$, $c$, $d_1$, $d_2$, $d_3$, $x$, $y$ are denoted by $A$, $B$, $C$, $D_1$, $D_2$, $D_3$, $X$, $Y$, respectively.


First, we prove that any of the segments $a$, $b$, and $c$ colours at least $k-6$ edges. The edges coloured by any $v$ consecutive colours form a matching, therefore $v$ consecutive colours can colour at most $|V(G)|/2 = k$ edges. Since $G$ is a snark, it has no two disjoint perfect matchings, therefore any two segments of length $v$ together colour at most $2k-1$ edges. If we put together segments $x$, $b$, $y$, and $c$, we obtain a segment of length $2v$, which colours at most $2k-1$ edges. Since the segments $d_1$, $d_2$, and $d_3$ colour together $7$ edges and $G$ has $3k$ edges, the remaining at least $k-6$ edges must be coloured by the segment $a$. This holds for the segment $c$ by symmetry. And the same approach can be also used for the segment $b$: if we group $a$ with $x$ and $y$ with $c$, we get two segments of length $v$, which together colour at most $2k-1$ edges. Consequently, $b$ colours at least $k-6$ edges.

Lemma~\ref{2u5} implies that any segment of length $v-2u$ colours at most $k-5$ edges.
Moreover, if two of the segments $a$, $b$, and $c$ coloured $k-5$ edges, we would have two disjoint perfect matchings in $G$, contradicting the assumption that $G$ is a snark.
Since the situation is symmetric with respect to replacing $a$ by $c$ and vice versa, we need to distinguish only three cases regarding the number of edges coloured by $a$, $b$, $c$.

\medskip

\noindent{\bf Case 1: each of the segments $a$, $b$, $c$ colours precisely $k-6$ edges.}
By counting the edges we obtain $3k=7+|A|+|X|+|B|+|Y|+|C|$, so $|X| + |Y|=11$. Therefore, at least one of the segments $x$ and $y$, say, $x$, colours at least $6$ edges. Since $y$ colours at least five edges (Lemma~\ref{2u5}), we know that $|X|=6$ and $|Y|=5$.

Consider the set $A\cup X$. This set of edges is a perfect matching, hence each edge from $D_2\cup D_3$ has both ends incident to an edge of $A\cup X$. However, no edge from $D_2\cup D_3$ can be adjacent to an edge of $A$ -- it would violate the condition that any two adjacent edges have colours that differ by at least $v$. Let $H$ be the subgraph of $G$ induced by $X$. The graph $H$ has $12$ vertices and we have shown that $H$ has at least $|X|+|D_2|+|D_3|=11$ edges. We show that there are even more edges belonging to $H$.

Consider the set $X\cup B$, which is a perfect matching of $G$. Therefore, each edge from $Y$ has both ends adjacent to an edge from $X\cup B$. Since it cannot be adjacent to an edge from $B$, it is on both ends adjacent to an edge from $X$. In other words, it belongs to $H$. Thus $H$ has at least $16$ edges.

As a subgraph of a cubic graph $G$, the graph $H$ is subcubic, that is, it has vertices of degree at most $3$. Therefore, there are at most $12\cdot 3-16\cdot 2 = 4$ edges separating $H$ from the rest of $G$. Moreover, $H$ contains a cycle of length at most $6$ by Lemma~\ref{pomocna}.

Consider the edge-cut $S$ separating $H$ from the rest of $G$. The graph $G-H$ has at most two components. If one of those components contained at most two vertices, then there is only one component in $G-H$ because $G$ is bridgeless, so $V(G-H)\le 2$. However, $|V(G-H)|=2k-12\ge 4$, a contradiction. Thus according to Lemma~\ref{pomocna2}, $S$ is cycle-separating.

\medskip

\noindent{\bf Case 2: the segment $a$ colours $k-5$ edges and $b$ and $c$ colour $k-6$ edges.}
The argument in Case 2 goes along the same line as in Case 1.
Since $|A|=k-5$, we have $|X| = 5$. The set $A\cup D_2\cup D_3$ is a perfect matching, therefore the set $Y\cup B$ contains at most $k-1$ edges. Consequently, $|Y| = 5$.
The set $A\cup X$ is a perfect matching of $G$, therefore the edges from $D_2\cup D_3$ are at both ends adjacent to edges of $X$. So the subgraph $H$ of $G$ induced by $X$ contains at least $10$ edges and has $10$ vertices. In fact, edges from the set $D_2\cup D_3\cup X$ form a cycle of length $10$, so $H$ is Hamiltonian.

Consider the set $M=X\cup B$. It is a matching with $k-1$ edges. The set $Y$ is a matching, therefore the $5$ edges in $Y$ have $10$ mutually distinct endpoints. So there are at most two endpoints that are not incident to an edge of $M$. Thus at least $3$ edges of $Y$ have both endpoints incident to an edge of $M$. Since no edge from $Y$ is adjacent to an edge of $B$, the three afore-mentioned edges of $Y$ belong to $H$, thus $H$ contains at least $13$ edges. A simple calculation regarding the bounded degrees of the vertices of $H$ shows that $H$ is separated by at most four edges from the rest of $G$.
Moreover, the cycle $C$ has at least three chords, thus there is a cycle of length at most $5$ in $H$.

Consider the edge-cut $S$ separating $H$ from the rest of $G$. The graph $G-H$ has at most two components. If one of those components contained at most two vertices, then there is only one component in $G-H$ because $G$ is bridgeless, so |$V(G-H)|\le 2$. However, $|V(G-H)|=2k-10\ge 6$, a contradiction. Thus according to Lemma~\ref{pomocna2}, $S$ is cycle-separating. 

\medskip

\noindent{\bf Case 3: the segment $b$ colours $k-5$ edges and $a$ and $c$ colour $k-6$ edges.}
This case is essentially the same as Case 2. From $|B|=k-5$, we immediately obtain $|X|=|Y|=5$. So $X\cup B$ is a perfect matching of $G$; consequently, any edge from $Y$ is adjacent at both ends to an edge from $X$ (it is not adjacent to any edge of $B$ because the edges from $B$ have colours that are too close to the colours of the edges from $Y$). So the subgraph $H$ of $G$ induced by $X$ contains a cycle of length $10$, where edges of this cycle alternately belong to $X$ and $Y$. At least three of the edges from $D_2\cup D_3$ must belong to $H$, because $A\cup X$ is a matching with $k-1$ edges in $G$. So $H$ has $10$ vertices and contains at least $13$ edges, therefore there are at most four edges separating $H$ from $G-H$. Moreover, $H$ is Hamiltonian and has girth at most $5$. The argument showing that $G-H$ contains a cycle is the same as in Case 2.
\end{proof}

\begin{remark}
A careful analysis of the proof of Lemma~\ref{ll1} shows that in a snark $G$
with $2k$ vertices and girth at least $6$ each system $d_1$, $d_2$, $d_3$, $x$, $y$
of $7u$ colours colours at least $18$ edges. Therefore, according to Proposition~\ref{counting} used in spirit of Remark~\ref{rem1}, $\chi_c'(G) \geq 3+
18/7k \geq 3+ 2.5714/k$.
\end{remark}

\section{Concluding remarks}

Lemma~\ref{ll1} put together with Proposition \ref{counting} gives a tight lower bound on the circular chromatic index of generalised type 1 Blanu\v sa snarks (their index was first determined in \cite{m}).
Indeed, according to Corollary \ref{corollary4cut}, the snark $B^1_m$ with $2k = 8m+2$ ($k\ge 9$) vertices from this class contains no $4$-edge-cut separating a Hamiltonian component with $10$ vertices or a component with $12$ vertices. Thus any segment of length $3u$ in a $(3v+u,v)$-edge-colouring of $B^1_m$ colours at least $8$ colours and then $\chi_c'(B_m^1)\ge 3+24/(9k-8)$. The actual value of $\chi_c'(B_m^1)$ is $3+24/(9k-9)$. It is an easy exercise to prove that there are no fractions $p/q$ with denominator at most $k$ lying between the above-given values. Finally, assume that $B_m^1$ has circular chromatic index $p/q=27k/(9k-8)$, where $p$ and $q$ are coprime. The greatest common divisor $d$ of $27k$ and $9k-8$ belongs to $\{1,2,3,4,6,8,12,24\}$. Since $d$ divides $9k-8=36m+1$, $d$ is odd, so $d$ is at most $3$. Then $p \ge 27k/d \ge 9k$, and this contradicts the well-known fact that each of the $p$ colours is used in every $(p,q)$-edge-colouring of the graph $B_m^1$ with only $3k$ edges (see \cite[
Proposition 2]{bh}). 

One may ask if the derived bounds can be practically used to determine the circular chromatic index of a given snark. The answer is that the derived bounds may be very helpful in certain cases, but it depends very heavily on the snark itself. On the one hand, the circular chromatic index $p/q$ of the Petersen graph is greater than $7/2$ due to Theorem~\ref{b2.5}, and since the numerator $p$ does not exceed $15$ (the number of edges), the fraction $p/q$ has to be $11/3$. On the other hand, for instance, most of the snarks on $26$ vertices have circular chromatic index $10/3$, which is far from the bounds we have proved. The derived bounds can be used to exclude some fractions from the set of possible values of circular chromatic index, but it is still not easy to determine which of the remaining fractions is the right one.

In addition to proving some bounds for particular values of the function $b(g, \lambda_c)$, we propose a conjecture about its behaviour.

\begin{conjecture}
The function $b(g, \lambda_c)$ is non-decreasing in both its parameters $g$ and $\lambda_c$.
\end{conjecture}

\bigskip

\noindent{\bf Acknowledgements.} The authors acknowledge support from the APVV grants 0223-10
and ESF-EC-0009-10 within the EUROCORES Programme EUROGIGA (project GReGAS) of the European Science
Foundation. Research of the first author was also supported by the APVV research grant
0111-07 and the VEGA research grant 1/2005/12.

\begin{thebibliography}{10}

\bibitem{agghtz}
P. Afshani, M. Ghandehari, M. Ghandehari, H. Hatami, R. Tusserkani, and X. Zhu, Circular chromatic index of graphs of maximum degree $3$, J. Graph Theory 49 (2005), 325--335.

\bibitem{bh}
J. A. Bondy, P. Hell, A note on the star chromatic number, J. Graph Theory 14 (1990), 479--482.

\bibitem{barborka}
B. Candr\'akov\'a, Circular chromatic index of regular graphs with maximum degree greater than three, Master's Thesis (2011), Comenius University.

\bibitem{goldbergove}
M. Ghebleh, The circular chromatic index of Goldberg snarks, Discrete Math. 307 (2007), 3220--3225.

\bibitem{blanusa2}
M. Ghebleh, Circular Chromatic Index of Generalized Blanusa Snarks, Electron. J. Combin. 15 (2008).

\bibitem{flower}
M. Ghebleh, D. Kráľ, S. Norine, and R. Thomas, The circular chromatic index of flower snarks, Electron. J. Combin. 13 (2006).

\bibitem{gheblehova dizertacka}
M. Ghebleh, Theorems and Computations in Circular Colourings of Graphs, PhD Thesis (2007), Simon Fraser University.

\bibitem{gtz}
L. A. Goddyn, M. Tarsi, and C. Zhang, On $(k, d)$-colorings and fractional
nowhere-zero flows, J. Graph Theory 28 (1998), 155--161.

\bibitem{hk}
A. Hackmann and A. Kemnitz, The circular chromatic index, Discrete Math. 286 (2004), 89--93.

\bibitem{kks}
T. Kaiser, D. Kráľ, and R. Škrekovski, A revival of the girth conjecture, J. Combin. Theory Ser. B (2004), 41--53.

\bibitem{konstrukcia}
R. Lukoťka and J. Mazák, Cubic graphs with given circular chromatic index, 
SIAM J. Discrete Math. Vol. 24 (2010), No. 3, 1091--1103.

\bibitem{rele}
R. Lukoťka and M. Škoviera, Real flow number and the cycle rank of a graph, J. Graph Theory 59 (2008), 11--16.

\bibitem{m}
J. Mazák, Circular chromatic index of type 1 Blanuša snarks, J. Graph Theory 59 (2008), 89--96.

\bibitem{diplomovka}
J. Mazák, Circular chromatic index of snarks, Master's thesis (2007), Comenius University, Bratislava.

\bibitem{ns}
R. Nedela and M. Škoviera, Decompositions and reductions of snarks, J. Graph Theory 22 (1996), 253--279.

\bibitem{nadolski}
A. Nadolski, The circular chromatic index of some class 2 graphs, Discrete Math. 307 (2007), 1447--1454.

\bibitem{panzhu}
Z. Pan and X. Zhu, Construction of graphs with given circular flow numbers, J. Graph Theory 43 (2003), 304--318.

\bibitem{vince}
A. Vince, Star chromatic number, J. Graph Theory 12 (1988), 551--559.

\bibitem{watkins1}
J. J. Watkins, Snarks, Ann. New York Acad. Sci. 576 (1989), 606--622.

\bibitem{zhu1}
X. Zhu, Circular chromatic number: a survey, Discrete Math. 229 (2001) 371--410.

\bibitem{zhu2}
X. Zhu, Recent developments in circular colourings of graphs, Topics in Discrete Mathematics, Springer, 2006, 497--550.

\end{thebibliography}

\newpage
\section*{Appendix: Auxiliary results}
\label{aux}

\begin{lemma}
\label{l1}
Let $k$ be an integer greater then $2$. There is no fraction $p/q$ with denominator not exceeding $k$, which satisfies the inequalities
\begin{equation}
\label{l1:nerovnosti}
{2\over k-{2\over 3}}\le {p\over q} < {2\over k-1}.
\end{equation}
\end{lemma}

\begin{proof}
We prove the lemma by contradiction. Assume that there is a fraction $p/q$ satisfying \eqref{l1:nerovnosti} such that $q \le k$.

If $p\ge 3$ then
$$\displaystyle {2\over k-1}>{p\over q}\ge {3\over q},$$
hence $2k \ge 2q > 3(k-1)$, contradicting the assumption $k>2$.

If $p\in\{1,2\}$ then $2q/p$ is an integer. The inequalities \eqref{l1:nerovnosti} imply that $2q/p$ lies in the interval $\displaystyle\left(k-1,k-2/3\right]$; that is impossible for an integer.
\end{proof}

\begin{lemma}
\label{pomocna2}
Let $G$ be a cubic graph. Every edge-cut $S$ of size at most $4$ is cycle-separating unless one of the components of $G-S$ has at most two vertices.
\end{lemma}

\begin{proof}
Let $C$ be one of the components of $G-S$ and let $m=|V(C)|$. If $C$ is acyclic then it has at most $m-1$ edges. On the other hand, the sum of the degrees of the vertices of $C$ is at least $3m-4$. Therefore, $3m-4\le 2|E(C)|\le 2(m-1)$, so $m\le 2$. Hence each component of $G-S$ with more than two vertices contains a cycle.
\end{proof}

\begin{lemma}
\label{pomocna}
Let $H$ be a subcubic graph (that is, $\Delta(H)\le 3$) with $12$ vertices and at least $16$ edges. Then $H$ contains a cycle of length at most $6$.
\end{lemma}

\begin{proof}
First, note that $H$ must contain a cycle because any forest on $12$ vertices has at most $11$ edges.
Let $C$ be a shortest cycle of $H$. Let $D = G - C$. Assume that the number $k$ of vertices of $C$ is at least $7$.

Since $C$ is a shortest cycle, it has no chords. Moreover, no vertex from $D$ has more than one neighbour on $C$. Therefore, the number of edges separating $C$ from $D$ is at most $12-k$. Since $12-k\le 5$, the graph $D$ does not contain a cycle; therefore, it is a forest and has at most $12-k-1=11-k$ edges.

Put together, the number of edges in the graph $H$ is at most $k + 12-k + 11-k = 23-k\le 16$. Since $H$ has precisely $16$ edges, the equality is achieved in all the inequalities we have used; hence $k=7$, each of the $5$ vertices of $D$ has exactly one neighbour on $C$, and there are four edges in $D$. Let $uv$ be an edge of $D$. Let $u'$ and $v'$, respectively, denote the neighbour of $u$ and $v$ lying on $C$. Then $u'$ and $v'$ have to be at distance at least $4$ along the circle $C$, otherwise we will have a cycle of length at most $6$ formed by the path $u'uvv'$ and the shortest path from $u'$ to $v'$ belonging to $C$. However, this is a contradiction, since any two vertices on $C$ are at distance at most $3$.
Therefore, $H$ contains a cycle of length at most $6$.
\end{proof}

The result of Lemma~\ref{pomocna} cannot be improved; there are exactly two subcubic graphs $H$ with $12$ vertices, $16$ edges and girth $6$.

\medskip

The purpose of the following lemma is to characterise all possible cycle-separating $4$-edge-cuts in generalised Blanu\v sa snarks.
Let $B$ denote the block obtained from the Petersen graph by removing two adjacent vertices; the block $B$ has $4$ dangling edges. The graph $B_m^1$ is composed of $m$ copies of $B$, we will call them {\it building blocks\/}, arranged in a sequence in such a way that a pair of dangling edges of the first and the last copy of $B$ are joined to a copy of complete graph on two vertices. 
We refer the reader to the article \cite{m} for more details about the construction of generalized type 1 Blanu\v sa snarks. 

We say that a $4$-edge-cut $S$ in the snark $B_m^1$ is {\it obvious} if each building block of $B_m^1$ is contained in a component of $B_m^1-S$.

\begin{lemma}
\label{lemma4cut}
Every cycle-separating $4$-edge-cut $S$ in $B_m^1$ is obvious.
\end{lemma}

\begin{proof}
Let $G=B_{2k}^1$ and let $S$ be a cycle-separating $4$-edge-cut of $G$. 
Note that there are two disjoint cycles $C_0$ and $C_1$ such that each of them passes through exactly $3$ vertices of each building block of $G$.
The rest of $G$ contains only edges joining $C_0$ to $C_1$ and components isomorphic to a subcubic graph $H$ containing two adjacent vertices and $4$ dangling edges. Each of the components of $G-S$ has to contain an edge both from $C_0$ and from $C_1$: if a component $K$ contained edges neither from $C_0$ nor $C_1$, it would not contain a cycle; if it contained only edges from $C_i$ and no edges from $C_{1-i}$, the edge-cut $S$ would have to contain at least $5$ edges since $K$ would contain at least one $5$-cycle.

Therefore each of the cycles $C_0$ and $C_1$ has to be cut in exactly two places, otherwise it is contained in only one component of $G-S$.
It is of no use to cut an edge of $C_0$ or $C_1$ that belongs to a building block $B$, because the copy of $H$ contained in this block would serve as a replacement for the edge we have cut and we would have to add another edge to the cut $S$. Hence we can confine ourselves to cutting edges outside of building blocks.
That means that each building block $B$ remains whole in a component of $G-S$; contracting each block $B$ allows us to immediately see that we have to cut both the edges separating two neighbouring building blocks if we cut one of them. So the cut $S$ must be obvious.

Similar ideas can be used to prove that each cycle-separating $4$-edge-cut in $B_{2k+1}^1$ is obvious.
\end{proof}

It is clear from Lemma~\ref{lemma4cut} that each component of $B_m^1$ separated by a cycle-separating $4$-edge-cut has $8$, $10$, or more than $16$ vertices. So there are no components with $12$ vertices. There is essentially only one way to create a component with $10$ vertices but this component is not Hamiltonian since it is isomorphic to the Petersen graph with two edges removed.

\begin{corollary}
\label{corollary4cut}
No $4$-edge-cut $S$ in $B_m^1$ separates a component with $12$ vertices or a Hamiltonian component with $10$ vertices. 
\end{corollary}


\end{document}

