% Template article for preprint document class `elsart'
% SP 2001/01/05

% Modified 2007/01/09 for CTW 2007
% Please find the original file at http://www.elsevier.com/

\documentclass{ctwart}
\usepackage{graphicx}

% Use the option doublespacing or reviewcopy to obtain double line spacing
% \documentclass[doublespacing]{elsart}

% if you use PostScript figures in your article
% use the graphics package for simple commands
% \usepackage{graphics}
% or use the graphicx package for more complicated commands
% \usepackage{graphicx}
% or use the epsfig package if you prefer to use the old commands
% \usepackage{epsfig}

% The amssymb package provides various useful mathematical symbols
\usepackage{amssymb}

\begin{document}
\setcounter{page}{51}
\begin{frontmatter}

% Title, authors and addresses

% use the thanksref command within \title, \author or \address for footnotes;
% use the corauthref command within \author for corresponding author footnotes;
% use the ead command for the email address,
% and the form \ead[url] for the home page:
% \title{Title\thanksref{label1}}
% \thanks[label1]{}
% \author{Name\corauthref{cor1}\thanksref{label2}}
% \ead{email address}
% \ead[url]{home page}
% \thanks[label2]{}
% \corauth[cor1]{}
% \address{Address\thanksref{label3}}
% \thanks[label3]{}


\title{Chromatic index of chordless graphs}


\author{R. Machado$^{a,b}$},
\author{C. Figueiredo$^{a}$}, and
\author{N. Trotignon$^{c}$},

\address{$^{a}$~COPPE - Universidade Federal do Rio de Janeiro}

\address{$^{b}$~Instituto Nacional de Metrologia, Normaliza\c{c}\~{a}o e Qualidade Industrial}

\address{$^{c}$~CNRS, LIAFA, Universit{\'e} Paris 7}

% use optional labels to link authors explicitly to addresses:
% \author[label1,label2]{}
% \address[label1]{}
% \address[label2]{}

\author{}

\address{}

\begin{abstract}
A graph $G$ is said to be \emph{chordless} if no cycle in $G$ has a chord. Chordless graphs are exactly the graphs whose line graphs are wheel-free, which implies a connection between the study of the chromatic index of chordless graphs and the study of the chromatic number of wheel-free graphs. For example, chordless graphs of maximum degree $\Delta=3$ are $\Delta$-edge-colourable, and this implies the 3-vertex-colorability of $\{$wheel,IS$K_{4}\}$-free graphs~\cite{ISK4-free}. In the present work we investigate the chromatic index of chordless graphs with higher degrees. We describe a decomposition result for chordless graphs and use this result to prove that every chordless graph of maximum degree $\Delta\geq3$ has chromatic index $\Delta$.

\end{abstract}

\begin{keyword}
% keywords here, in the form: keyword \sep keyword
chordless graphs \sep chromatic index \sep edge-colouring
\end{keyword}

\end{frontmatter}

% main text





\section{Introduction}
\label{s:introduction}

Let $G=(V,E)$ be a simple graph. The maximum degree of a vertex in $G$ is denoted
$\Delta(G)$. A \emph{$k$-edge-colouring} of $G$ is a function $\pi:E\rightarrow\{1,2,...,k\}$ such that no two adjacent edges receive the same colour $c\in\{1,2,...,k\}$. The \emph{chromatic index} of $G$, denoted by $\chi'(G)$, is the least $k$ for which $G$ has a $k$-edge-colouring. Vizing's theorem~\cite{Vizing} states that $\chi'(G)=\Delta(G)$, and $G$ said to be \emph{Class~1}, or $\chi'(G)=\Delta(G)+1$, and $G$ said to be \emph{Class~2}.
Edge-colouring is NP-complete for regular graphs~\cite{Holyer,Leven} of degree $\Delta\geq3$. The problem is NP-complete also for the following classes~\cite{CaiEllis}: comparability (hence perfect) graphs, line graphs of bipartite graphs (hence line graphs and clique graphs), \{induced $k$-cycle\}-free graphs ($k\geq3$), cubic graphs of girth $k$ ($k\geq4$). Graph classes for which edge-colouring is polynomially solvable include the following: bipartite graphs~\cite{Johnson}, split-indifference graphs~\cite{SplitIndifference}, series-parallel graphs (hence outerplanar)~\cite{Johnson}, $k$-outerplanar graphs~\cite{Bodlaender} ($k\geq1$). The complexity of edge-colouring is unknown for several well-studied strong structured graph classes, for which only partial results have been reported, such as cographs~\cite{Barbosa}, join graphs~\cite{join1}, planar graphs~\cite{Sanders}, chordal graphs, and
several subclasses of chordal graphs such as indifference graphs~\cite{Celina}, split graphs~\cite{ChenFuKo} and interval graphs~\cite{Bojarshinov}.
%The reader will see in Figure~\ref{f:classes-complexity} the current status of edge-colouring in restricted graph classes.
%%===============================
%\begin{figure}[hbt]
%\label{f:classes-complexity}
%\centerline{\includegraphics[width=300pt]{classes-complexity.png}}
%\caption{Current status of edge-colouring in restricted graph classes.}
%\end{figure}
%%===============================
%

L{\^e}v{\'e}que, Maffray and Trotignon~\cite{ISK4-free} studied the class of chordless graphs, which are the graphs whose cycles are all chordless. There are two main motivations to study the class.
The first motivation is its relation with the the class of wheel-free graphs: chordless graphs are exactly the graphs whose line graphs are wheel-free. Hence, the study of the chromatic index of chordless graphs has importance to the study of the (vertex) chromatic number of wheel-free graphs and subclasses. For example, the 3-vertex-colourability of $\{$wheel, IS$K_{4}\}$-free graphs is consequence~\cite{ISK4-free} of the fact that chordless graphs of maximum degree~3 are Class~1.
The second motivation for the study of the chromatic index of chordless graph is the fact that they are a subclass of the class of graphs that do not contain, as induced subgraph, a cycle with unique chord, called \emph{unichord-free} graphs. The edge-colouring problem is NP-complete when restricted to unichord-fre graphs~\cite{Edge-tv}; hence, it is of interest to determine subclasses of unichord-free graphs for which ege-colouring is polynomial.

%The remainder of the paper is organized as follows. In Section~\ref{s:structure}, we review known results on the structure of chordless graphs and prove the existence of an extremal decomposition. In Section~\ref{s:edge-colouring} we show how to determine the chromatic index of a chordless of maximum degree $\Delta\geq3$ in polynomial time. In Section~\ref{s:edge-colouring} we show how to determine the total chromatic number of a chordless of maximum degree $\Delta\geq3$ in polynomial time. Section~\ref{s:final} contains final considerations on this work.



\section{Structure of chordless graphs}
\label{s:structure}

We describe a decomposition result for chordless graphs. This result is used in Section~\ref{s:edge-colouring} to determine the chromatic index of chordless graphs.

%Given a graph $F$, we say that a graph $G$ {\em contains} $F$ if graph $F$ is
%isomorphic to an induced subgraph of $G$.  A graph $G$ is \emph{$F$-free} if $G$ does not contain $F$.  A \emph{cycle} $C$ in a graph
%$G$ is a sequence of vertices $v_1v_2\ldots v_nv_1$, that are
%distinct except for the first and the last vertex, such that for
%$i=1, \ldots ,n-1$, $v_iv_{i+1}$ is an edge and $v_nv_1$ is an
%edge -- we call these edges \emph{the edges of $C$}. An edge of $G$ with both
%endvertices in a cycle $C$ is called a \emph{chord} of $C$ if it is not an
%edge of $C$. One can similarly define a path and a chord of a
%path. A {\em hole} is a chordless cycle of length at least four and an $\ell$\emph{-hole} is a hole of length $\ell$. A
%\emph{triangle} is a cycle of length~3 and a \emph{square} is a 4-hole. A graph is called a \emph{cycle-graph} (resp. \emph{path-graph}) if it has a cycle (resp. path) that contains every vertex and has no chord.

A graph is \emph{strongly 2-bipartite} if it is square-free and bipartite with bipartition
$(X,Y)$ where every vertex in $X$ has degree~2 and every vertex in $Y$ has degree at least~3.
A graph is \emph{sparse} if every edge is incident to a vertex of degree at most~2.
A \emph{cutset} of a graph $G$ is a set of vertices whose exclusion disconnects $G$. The following cutsets are used in the known decomposition theorems of the class of chordless graphs:

\begin{itemize}
	\item A \emph{1-cutset} of a connected graph $G=(V,E)$ is a node $v$ such that $V$ can be partitioned into sets $X$, $Y$ and $\{ v \}$, so that there is no edge between $X$ and $Y$. We say that $(X, Y,v)$ is a \emph{split} of this 1-cutset.
	\item  A \emph {proper 2-cutset} of a connected graph $G=(V,E)$ is a pair of non-adjacent nodes $a, b$, both of degree at least three, such that $V$ can be partitioned into sets $X$, $Y$ and $\{ a,b \}$ so that: $|X|\geq 2$, $|Y| \geq 2$; there is no edge between $X$ and $Y$, and both $G[X \cup \{ a,b \}]$ and $G[Y \cup \{ a,b \}]$ contain an $ab$-path.  We say that $(X, Y, a, b)$ is a \emph{split} of this proper 2-cutset.
\end{itemize}

A graph is called {\em basic} if: (1) is cycle with at least four vertices or strongly 2-bipartite; and (2) has no decomposition by 1-cutset or proper 2-cutset.

The \emph{block} $G_X$ (resp. $G_Y$) of a graph $G$ with respect to a 1-cutset with split $(X, Y, v)$ is
$G[X\cup \{ v \} ]$ (resp. $G[Y\cup \{ v\} ]$). The \emph{blocks} $G_X$ and $G_Y$ of a graph $G$ with respect to a proper 2-cutset with split $(X, Y, a, b)$ are defined as follows. If a node $c$ has only neighbors $a$ and $b$ in $G$, then $G_X:=G[X \cup \{ a,b,c \}]$ (resp. $G_Y:=G[Y \cup \{ a,b,c \}]$). Otherwise, $G_X$ (resp. $G_Y$) is obtained from $G[X\cup \{ a,b\}]$ (resp. $G[Y\cup \{ a,b\}]$) by adding new node $c$ adjacent to $a$ and $b$.

Theorem~\ref{t:chordless}~\cite{ISK4-free} describes a decomposition of chordless graphs into sparse graphs. As we state in Theorem~\ref{t:sparse}, sparse graphs can be decomposed by proper 2-cutsets. From Theorems~\ref{t:chordless} and~\ref{t:sparse}, we state the new decomposition result of Theorem~\ref{t:new-chordless}. Finally, Theorem~\ref{t:extremal} proves that a non-basic chordless graph has a decomposition in which (at least) one of the blocks is basic.

\begin{thm}
\label{t:chordless}
\emph{(L{\'e}v{\^e}que, Maffray and Trotignon~\cite{ISK4-free})} If $G$ is a chordless graph, then either $G$ is sparse or $G$ admits a 1-cutset or $G$ admits a proper 2-cutset.
\end{thm}

%As we discuss in the following observation~\cite{Borodin}, for the goal of edge-colouring, we only may assume the graphs are \textbf{biconnected}.
%
%\begin{observation}
%Let $G$ be a connected graph with a 1-cutset $v$ with split $(X,Y,v)$. The chromatic index of $G$ is $\chi'(G)=\max\{\chi'(G_{X}),\chi'(G_{Y}),\Delta(G)\}$.
%\label{o:edge-colour-biconnected}
%\end{observation}
%
%By Observation~\ref{o:edge-colour-biconnected}, if both blocks $G_{X}$ and $G_{Y}$ are $\Delta(G)$-edge-colourable, then so is $G$. That is, once we know the chromatic index of the biconnected components of a graph, it is easy to determine the chromatic index of the whole graph. So, we may focus our investigation on the biconnected chordless graphs.


\begin{thm}
\label{t:sparse}
If $G$ is sparse graph with $\Delta(G)\geq3$ then either $G$ is strongly 2-bipartite or $G$ admits 1-cutset or $G$ admits proper 2-cutset.
\end{thm}

%\begin{pf}
%Let $G$ be a sparse graph and let $V_{h}:=\{v\in V(G)|deg(v)\geq3\}$ be the set of vertices with degree at least~3. We may assume that $G$ is biconnected, otherwise $G$ has a 1-cutset.
%
%Suppose that $G$ is not strongly 2-bipartite. Then, either $G$ has a square or $V_{l}:=V(G)\setminus V_{h}$, the set of the vertices with degree~2 (because $G$ is assumed to be biconnected), is \textbf{not} a stable set.
%
%Suppose that $G$ has a square $abcd$. If none of $a,b,c,d$ has degree $\geq3$, then $G$ is disconnected. If only one of $a,b,c,d$ has degree $\geq3$, then $G$ has a 1-cutset. If more than two of of $a,b,c,d$ have degree $\geq3$, then $G$ is not sparse. So, exactly two of $a,b,c,d$ have degree $\geq3$, and these vertices must be non-adjacent, say $a$ and $c$. Then, $(a,c,\{b,d\},V\setminus\{a,b,c,d\})$ is the split of a proper 2-cutset of $G$.
%
%Now, suppose that $V_{l}$ is not a stable set. There is an edge $uv$ such that $u,v\in V_{l}$. Let $P$ be the connected component of $G[V_{l}]$ containing $u$ and $v$. Observe that $V[V_{l}]$ is a collection of paths, so that $P$ itself is a path. Let $x'$ and $y'$ be the vertices of $P$ with degree~1 and let $x$ (resp. $y$) be the unique neighbor of $x'$ (resp. $y'$) in $V_{h}$. Then $(V(P),V(G)\setminus\{x,y\}\setminus V(P),x,y)$ is the split of a proper 2-cutset of $G$.
%\end{pf}
%

\begin{thm}
\label{t:new-chordless}
If $G$ is chordless graph then either $G$ is strongly 2-bipartite or $G$ is cycle on at least~4 vertices or $G$ admits 1-cutset or $G$ admits proper 2-cutset.
\end{thm}

\begin{thm}
\label{t:extremal}
If $G$ is a biconnected non-basic chordless graph then $G$ admits proper 2-cutset with split $(X,Y,a,b)$ such that $G_{X}$ is basic.
\end{thm}


\section{Chromatic index of chordless graphs}
\label{s:edge-colouring}

We apply the structure results of Section~\ref{s:structure} to show
that every chordless graph of maximum degree at least~3 is Class~1.
We show how to $\Delta(G)$-edge-colour a graph
$G\in\mathcal{C}'$ by combining $\Delta(G)$-edge-colourings of its
blocks with respect to a decomposition by proper 2-cutset.

\begin{lem}
\label{l:edge-colouring}
Let $G$ be a chordless graph of maximum degree $\Delta\geq3$ and let $(X,Y,a,b)$ be a split of proper 2-cutset, in such a way that $G_{X}$ is basic. If $G_{Y}$ is $\Delta$-edge-colourable, then $G$ is $\Delta$-edge-colourable.
\end{lem}

\begin{thm}
\label{t:ChordlessClass1}
Every chordless graph of maximum degree $\Delta\geq3$ is Class~1.
\end{thm}

\begin{pf}
\textbf{Sketch.} Assume $G$ biconnected. If $G$ is basic, then $G$ is strongly 2-bipartite, hence Class~1. If $G$ is not basic, then $G$ has proper 2-cutset with split $(X,Y,a,b)$ such that $G_{X}$ is basic. Assume, as induction hypothesis, that $G_{Y}$ is $\Delta$-edge-colourable. By Lemma~\ref{l:edge-colouring}, graph $G$ is $\Delta$-edge-colourable.
\end{pf}



\def\refname{\normalsize\bf References}
\begin{thebibliography}{9}

\bibitem{Barbosa}
M. M. Barbosa, C. P. de Mello, and J. Meidanis. \emph{Local conditions for edge-colouring of cographs}. Congr. Numer. \textbf{133} (1998) 45--55.

%\bibitem{BehzadTese}
%Behzad, M.: 1965, \emph{Graphs and their chromatic numbers.}
%Doctoral Thesis - Michigan State University.
%
%\bibitem{Beineke}
%L. W. Beineke. (1968), \emph{Derived graphs of digraphs}. Beiträge zur Graphentheorie - Leipzig (1968) 17-–33.

\bibitem{Bodlaender}
H. L. Bodlaender. \emph{Polynomial algorithms for graph isomorphism and chromatic index on partial k-trees}. J. Algorithms \textbf{11} (1990) 631--643.

\bibitem{Bojarshinov}
V. A. Bojarshinov. \emph{Edge and total colouring of interval graphs}. Discrete Appl. Math. \textbf{114} (2001) 23--28.

%\bibitem{Borodin}
%O. V. Borodin, A. V. Kostochka, and D. R. Woodall.
%\emph{List edge and list total colourings of multigraphs}.
%J. Combin. Theory Ser. B \textbf{71} (1997) 184--204.

\bibitem{CaiEllis}
L. Cai and J. A. Ellis. \emph{NP-Completeness of edge-colouring some restricted graphs}. Discrete Appl. Math. \textbf{30} (1991) 15--27.

%\bibitem{petals}
%D. Cariolaro and G. Cariolaro. \emph{Colouring the petals of a graph}. Electron. J. Combin. \textbf{10} (2003) \#R6.

\bibitem{ChenFuKo}
B. L. Chen, H.-L. Fu, and M. T. Ko. \emph{Total chromatic number and chromatic index of split graphs}. J. Combin. Math. Combin. Comput. \textbf{17} (1995) 137--146.

%\bibitem{threeinatree}
%Chudnovsky, M., Seymour, P., The three-in-a-tree-problem, Manuscript.

%\bibitem{balanced}
%Conforti, M., Cornuejols, G., Kapoor, A. and Vuskovic, K.:2006, Balanced Matrices, \emph{Discrete Mathematics}, \textbf{306}(19-20), 2411--2437.

\bibitem{Celina}
C. M. H. de Figueiredo, J. Meidanis, C. P. de Mello, and C. Ortiz. \emph{Decompositions for the edge colouring of reduced indifference graphs}. Theoret. Comput. Sci. \textbf{297} (2003) 145--155.

%\bibitem{Roxinho}
%C. M. H. de Figueiredo, J. Meidanis, and C. P. de Mello. \emph{Local conditions for edge-coloring.} J. Combin. Math. Combin. Comput. \textbf{32} (2000) 79--91.

\bibitem{join1}
C. De Simone and C. P. de Mello. \emph{Edge-colouring of join graphs}.  Theoret. Comput. Sci. \textbf{355} (2006) 364--370.

%\bibitem{join2}
%C. De Simone and A. Galluccio. \emph{Edge-colouring of regular graphs of large degree}.  Theoret. Comput. Sci. \textbf{389} (2007) 91--99.

%\bibitem{Gyarfas}
%A. Gy{\'a}rf{\'a}s. \emph{Problems from the world surrounding perfect graphs}.  Zastos. Mat. \textbf{19} (1987) 413--441.

\bibitem{Holyer}
I. Holyer. \emph{The NP-completeness of edge-colouring}.  SIAM J. Comput. \textbf{10} (1982) 718--720.

\bibitem{Johnson}
D. S. Johnson. \emph{The NP-completeness column: an ongoing guide}. J. Algorithms \textbf{6} (1985) 434--451.

%\bibitem{core2}
%A. J. W. Hilton and Cheng Zhao. \emph{On the edge-colouring of a graph whose core has maximum degree two}. J. Combin. Math. Combin. Comput. \textbf{21} (1996) 97--108.

%\bibitem{conjecture}
%A. G. Chetwynd and A. J. W. Hilton. \emph{Star multigraphs with three vertices of maximum degree}. Math. Proc. Cambridge Philos. Soc. \textbf{100} (1986) 303--317.

%\bibitem{Hoffman}
%D. G. Hoffman and C. A. Rodger. \emph{The chromatic index of complete multipartite graphs}. J.Graph Theory \textbf{16} (1992) 159--163.

\bibitem{Leven}
D. Leven and Z. Galil. \emph{NP-completeness of finding the chromatic index of regular graphs}. J. Algorithms \textbf{4} (1983) 35--44.

\bibitem{ISK4-free}
B. L{\'e}v{\^e}que, F. Maffray, and N. Trotignon. \emph{On graphs with no induced subdivision of $K_{4}$.} Preprint available at \texttt{www.liafa.jussieu.fr/~trot}.

%\bibitem{JoinCobipartite}
%R. C. S. Machado and C. M. H. de Figueiredo. \emph{Decompositions for edge-coloring join graphs and cobipartite graphs}. To appear in Discrete Appl. Math.

%\bibitem{Niessen}
%T. Niessen.
%\emph{How to find overfull subgraphs in graphs with large maximum degree. II.}  Electron. J. Combin. \textbf{8} (2001) \#R7.

\bibitem{SplitIndifference}
C. Ortiz, N. Maculan, and J. L. Szwarcfiter. \emph{Characterizing and edge-colouring split-indifference graphs}. Discrete Appl. Math. \textbf{82} (1998) 209--217.

\bibitem{Edge-tv}
R. Machado, C. Figueiredo, and K. Vu{\v s}kovi{\'c}. \emph{Chromatic index of graphs with no cycle with unique chord}. Theoret. Comput. Sci. \textbf{411} (2010) 1221--1234.

%\bibitem{Planthold}
%M. Plantholt. \emph{The chromatic index of graphs with a spanning star}. J. Graph Theory \textbf{5} (1981) 45--53.

%\bibitem{forbidden}
%B. Randerath and I. Schiermeyer. \emph{Vertex colouring and forbidden subgraphs---a survey}.  Graphs Combin. \textbf{20} (2004) 1--40.

\bibitem{Sanders}
D. P. Sanders and Y. Zhao. \emph{Planar graphs of maximum degree seven are class I}. J. Combin. Theory Ser. B \textbf{83} (2001) 201--212.

%\bibitem{Steffen}
%E. Steffen. \emph{Classifications and characterizations of snarks }. Discrete Math. \textbf{188} (1998) 183--203.

\bibitem{tv}
N. Trotignon and K. Vu{\v s}kovi{\'c}.
\emph{A structure theorem for graphs with no cycle with a unique chord and
its consequences}. J. Graph Theory \textbf{63} (2010) 31--67.

\bibitem{Vizing}
V. G. Vizing. \emph{On an estimate of the chromatic class of a
$p$-graph} (in russian). Diskret. Analiz \textbf{3} (1964) 25--30.

%\bibitem{VizingPlanar}
%V. G. Vizing. \emph{Critical graphs with given chromatic index} (in russian). Diskret. Analiz \textbf{5} (1965) 9--17.

%\bibitem{West}
%D. B. West. \emph{Introduction to Graph Theory.} Second edition. Prentice Hall (2001).

\end{thebibliography}




\end{document}

