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

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

\documentclass{ctwart}


\newtheorem{theorem}{Theorem}
\newtheorem{conjecture}{Conjecture}
\newtheorem{corollary}{Corollary}
\newtheorem{definition}{Definition}
\newtheorem{lemma}{Lemma}
\newtheorem{proposition}{Proposition}

% 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}{129}
\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{Maximum $\Delta$-edge-colorable subgraphs of class II graphs}

\author[label1]{Vahan V. Mkrtchyan,\thanksref{label2}}
\ead{vahanmkrtchyan2002@\{ysu.am, ipia.sci.am,yahoo.com\}}
% \ead[url]{home page}
 \thanks[label2]{The author is supported by a fellowship from the Heinrich Hertz-Stiftung}
\author[label1]{Eckhard Steffen}
\ead{es@upb.de}

%\title{Maximum $\Delta$-edge-colorable subgraphs of class II graphs}

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

%\author[label]{Vahan V. Mkrtchyan,} \author[label]{Eckhard Steffen}
\address[label1]{Paderborn Institute for Advanced Studies in Computer Science and Engineering,
Paderborn University, Warburger Str. 100, 33098 Paderborn, Germany}

\begin{keyword}
% keywords here, in the form: keyword \sep keyword
maximum $\Delta$-edge-colorable subgraph \sep matching \sep $2$-factor \sep edge-chromatic number \sep chromatic index \sep class II graph
\end{keyword}

\end{frontmatter}

% main text
\section{Introduction}
\label{}

% The Appendices part is started with the command \appendix;
% appendix sections are then done as normal sections
% \appendix

We consider finite, undirected graphs $G=(V,E)$ with vertex set $V$
and edge set $E$. The graphs might have multiple edges but no loops.
Let $\delta(G)$ and $\Delta(G)$ denote the minimum and maximum degree
of a graph $G$, respectively. A partial proper $t$-edge-coloring of a graph $G$ is an assignment
of colors $\{1,...,t\}$ to some edges of $G$ such that adjacent
edges receive different colors. If $\theta$ is a partial proper $t$-edge-coloring
of a graph $G$ and $P$ is a path, then $P$ is called to be $\alpha-\beta$
alternating, if the edges of $P$ are colored by the colors $\alpha$
or $\beta$. 
A partial proper $t$-edge-coloring of a graph $G$ is called a proper
$t$-edge-coloring (or just $t$-edge-coloring) of $G$ if all edges
are assigned some color. The least number $t$ for which $G$ has
a $t$-edge-coloring is called the chromatic index of $G$ and is
denoted by $\chi'(G)$. The classical theorems of Shannon and Vizing
state:

\begin{theorem}\label{Shannon}(Shannon) For any graph $G$: $\Delta(G)\leq\chi'(G)\leq\lfloor\frac{3\Delta(G)}{2}\rfloor$.
\end{theorem}

\begin{theorem}\label{Vizing}(Vizing) For any graph $G$: 
$\Delta(G)\leq\chi'(G)\leq\Delta(G)+\mu(G)$, where $\mu(G)$ is the maximum 
multiplicity of an edge in $G$. 
\end{theorem}

A graph $G$ with $\chi'(G) = \Delta(G) = \Delta$ is {\em class I}, 
otherwise it is {\em class II}. 
There are long standing open conjectures on the class II graphs, cf. \cite{Jensen_Toft}. 
It is a notorious difficult open problem to characterize class II graphs or even to obtain 
some insight into their structural properties. This paper focuses on the $\Delta$-colorable part
of graphs. A subgraph $H$ of $G$ is called {\em maximum} $\Delta$-edge-colorable, if it is $\Delta$-edge-colorable
and contains as many edges as possible. The fraction $|E(H)|/|E(G)|$ is subject of many papers,
and e.g. lower bounds are proved for cubic, subcubic or 4-regular graphs, \cite{A_Haas,part1,Rizzi_2009}. 
The aim of this paper is to prove a general best possible lower bound for all graphs.

Let $H$ be a maximum $\Delta$-edge-colorable
subgraph of $G$, which is properly colored with $\{1,...,\Delta\}$.
Usually, we will refer to edges of $E(G)\backslash E(H)$ as uncolored
edges. For a vertex $v$ of $G$ let $C(v)$ be the set of colors
that appear at $v$, and $\bar{C}(v)=\{1,...,\Delta\}\backslash C(v)$
be the set of colors which are missing at $v$.
Let $e=(v,u)\in E(G)\backslash E(H)$ be an uncolored edge, and $\alpha\in\bar{C}(u)$,
$\beta\in\bar{C}(v)$. Since $H$ is a maximum $\Delta$-edge-colorable
subgraph of $G$, we have that $\alpha\in C(v)$ and $\beta\in C(u)$.
Consider the $\alpha-\beta$ alternating path $P$ starting from the
vertex $v$. Again, since $H$ is a maximum $\Delta$-edge-colorable
subgraph of $G$, the path $P$ ends in $u$. Thus $P$ is an even
path, which together with the edge $e$ forms an odd cycle. We will
denote this cycle by $C_{\alpha,\beta,H}^{e}$. If the subgraph $H$
is fixed, then we will shorten the notation to $C_{\alpha,\beta}^{e}$.

The cycles corresponding to uncolored edges, that are the cycles $C_{\alpha,\beta}^{e}$,
play a central role in \cite{SteffenClassification,Steffen} in the
study of cubic graphs. One aim of the present paper is to generalize
some of these results to arbitrary graphs, and to investigate the
maximum $\Delta$-edge-colorable subgraphs. We show that any set of
vertex disjoint cycles of a graph $G$ with $\Delta(G)\geq3$ can be extended to a maximum
$\Delta$-edge-colorable subgraph of $G$. In particular, any $2$-factor
of a graph with maximum degree at least three can be extended to such a subgraph.

For a graph $G$ let $r_{e}(G)$ denote the minimum
number of edges that should be removed from $G$ in order
to obtain a graph $H$ with $\chi'(H)=\Delta(G)$. Let
$G$ be a graph and $\phi$ a $\chi'(G)$-coloring of $G$ with
$\chi'(G)=\Delta(G)+k$ ($k\geq1$). Let $r'_{\phi}(G)=\min\sum_{j=1}^{k}|\phi^{-1}(i_{j})|$,
and define $r'_{e}(G)=\min_{\phi}r'_{\phi}(G)$ as the minimum size
of the union of $k$ color-classes in a $\chi'(G)$-edge-coloring
of $G$.

Clearly, $r_{e}(G)=|E(G)|-|E(H)|$, where $H$ is a maximum $\Delta$-edge-colorable
subgraph of $G$. In  \cite{part2} it is shown that the complement of any maximum
$3$-edge-colorable subgraph of a cubic graph is a matching, and hence $r_{e}(G)=r'_{e}(G)$
for cubic graphs.  This paper generalizes this result to simple graphs. 
We further prove some bounds for the vertex degrees of a maximum $\Delta(G)$-colorable
subgraph $H$.

\section{The main results}\label{}

The key property of cycles corresponding to uncolored edges that is used in \cite{SteffenClassification,Steffen} is their vertex-disjointness. There are many examples showing that they can have even common edges in the general case. Despite this, it turns out that, as Theorem \ref{assignment} demonstrates below, the edge-disjointness of the cycles can be preserved. 

\begin{theorem}\label{assignment}Let $H$ be any maximum $\Delta(G)$-edge-colorable
subgraph of a graph $G$, and let $E(G)-E(H)=\{e_{i}=(u_{i},v_{i})|1\leq i\leq n\}$
be the set of uncolored edges. Assume that $H$ is properly edge-colored
with colors $1,\ldots,\Delta(G)$. Then there is an assignment of
colors $\alpha_{1}\in\overline{C}(u_{1}),\beta_{1}\in\overline{C}(v_{1}),\ldots,\alpha_{n}\in\overline{C}(u_{n}),\beta_{n}\in\overline{C}(v_{n})$
to the uncolored edges such that $
E(C_{\alpha_{i},\beta_{i}}^{e_{i}})\cap E(C_{\alpha_{j},\beta_{j}}^{e_{j}})=\emptyset$,
for all $1\leq i<j\leq n$. \end{theorem}

The next Theorem generalizes the result of \cite{part2} that any
$2$-factor of a cubic graph can be extended to a maximum $3$-edge-colorable
subgraph to arbitrary graphs.

\begin{theorem}\label{CycleSystemExtension}Let $\bar{F}$ be any
set of vertex-disjoint cycles of a graph $G$ with $\Delta=\Delta(G)\geq3$. Then there is a maximum
$\Delta$-edge-colorable subgraph $H$ of $G$, such that $E(\bar{F})\subseteq E(H)$.
\end{theorem}

\begin{corollary}\label{2factorExtension}Let $\bar{F}$ be any $2-$factor
of a graph $G$ with $\Delta(G)\geq3$. Then there is a maximum $\Delta(G)$-edge-colorable
subgraph $H$ of $G$, such that $E(\bar{F})\subseteq E(H)$. \end{corollary}

Let $G$ be a graph. The length of the shortest (odd) cycle of the
underlying simple graph of $G$ is called {\em (odd) girth} of $G$.
If $X\subseteq V(G)$, then $\partial_{G}(X)$ denotes
the set of edges with precisely one end in $X$. 

\begin{theorem}\label{cutCondition} Let $H$ be any maximum $\Delta(G)$-edge-colorable
subgraph of a graph $G$. Then 
\begin{enumerate}
\item $|\partial_{H}(X)|\geq\lceil\frac{|\partial_{G}(X)|}{2}\rceil$ for each $X\subseteq V(G)$. 
\item $d_{H}(x)\geq\lceil\frac{d_{G}(x)}{2}\rceil$ for each vertex $x$ of $G$. 
\item $\delta(H)\geq\lceil\frac{\delta(G)}{2}\rceil$.
\end{enumerate}
The bounds are best possible. 
\end{theorem}

\begin{theorem}\label{Multigraphgirth} Let $G$ be a graph with girth $g \in \{2k, 2k+1\}$ 
($k\geq 1$), and $H$ a maximum $\Delta(G)$-edge-colorable
subgraph of $G$, then $|E(H)| \geq \frac{2k}{2k+1}|E(G)|$, 
and the bound is best possible. 
\end{theorem}

\begin{theorem}\label{MatchingComplement} Every simple graph
$G$ contains a maximum $\Delta$-edge-colorable subgraph such
that the uncolored edges form a matching. \end{theorem}

Theorem \ref{MatchingComplement} is equivalent to: 

\begin{theorem} For any simple graph $G$: $r_{e}(G)=r'_{e}(G)$.
\end{theorem}

It can be shown that a maximum $\Delta$-edge-colorable subgraph of a multigraph can be class II as well. 
This cannot be the case for simple graphs as the following theorem shows.  
 
\begin{theorem} \label{equality} Let $H$ be a maximum $\Delta(G)$-edge-colorable
subgraph of a simple graph $G$, then $\Delta(H)=\Delta(G)$, i.e. $H$ is class I.
\end{theorem}

Theorem \ref{MatchingComplement} says, that every simple class II graph $G$ has a 
maximum $\Delta$-colorable subgraph $H$, such that $\chi'(G \backslash E(H))=1$. 
We believe that this can be generalized to multigraphs:

\begin{conjecture} \label{k_matching} Let $G$ be a graph with $\chi'(G)=\Delta(G)+k$ 
($k \geq 0$).
Then there is a maximum $\Delta(G)$-colorable subgraph $H$ of $G$
such that $\chi'(G\backslash E(H))=k$. \end{conjecture} 

This conjecture is equivalent to the following statement.

\begin{conjecture} For any graph $G$: $r_{e}(G)=r'_{e}(G)$. \end{conjecture}

\begin{thebibliography}{7}
% \bibitem{label}
% Text of bibliographic item

% notes:
% \bibitem{label} \note

% subbibitems:
% \begin{subbibitems}{label}
% \bibitem{label1}
% \bibitem{label2}
% If there is a note, it should come last:
% \bibitem{label3} \note
% \end{subbibitems}

\bibitem{A_Haas} M. O. Albertson, R. Haas, Parsimonious edge coloring,  Disc. Math.  148  (1996) 1-7

\bibitem{Kierstead}H. A. Kierstead, On the chromatic index of multigraphs without large triangles, J. Comb. Theory, Ser. B 36 (1984) 156-160

\bibitem{part1} V. V. Mkrtchyan, S. Petrosyan, G. Vardanyan, On disjoint
matchings in cubic graphs, Disc. Math. to appear, (available at: http://arxiv.org/abs/0803.0134)

\bibitem{part2} V. V. Mkrtchyan, S. Petrosyan, G. Vardanyan, On disjoint
matchings in cubic graphs: maximum $3$-edge-colorable subgraphs,
under review, (available at: http://arxiv.org/abs/0909.2767)

\bibitem{Rizzi_2009} R. Rizzi, Approximating the maximum 3-edge-colorable subgraph problem, Disc. Math. 309 (2009) 4166-4170.

\bibitem{SteffenClassification} E. Steffen, Classifications and characterizations
of snarks, Disc. Math. 188 (1998) 183-203.

\bibitem{girthEckhard} E. Steffen, A refinement of Vizing's theorem.
Disc. Math. 218 (2000) 289-291.

\bibitem{Steffen} E. Steffen, Measurements of edge-uncolorability,
Disc. Math. 280 (2004) 191-214.

\bibitem{Jensen_Toft} T. R. Jensen, B. Toft, Graph coloring problems, 
Wiley-Interscience Series in Discrete Mathematics and Optimization, 
John Wiley \& Sons, Inc., New York, 1995.

\end{thebibliography}

\end{document}

