\documentclass{article}
\usepackage{amsthm}
\input{18313-preamble}

\begin{document}
\lecture{2004/02/13}{Dan Ports}{2004/02/26}{drkp@mit.edu}
\begin{center}
  \Large{Independent Sets and 2-Factors in Edge-Chromatic-Critical
  Graphs} \\
  \large{Grunewald and Steffen, J Graph Theory 45: 113 118, 2004} \\
  \large{Lecturer: Venkat Chandar \\ Scribe: Dan Ports}
\end{center}


\section{Definitions}
\label{sec:definitions}

\begin{description}
\item[Simple graphs] We concern ourselves with simple graphs: at most
  one edge between any two vertices.
\item[Degree] Let $\Delta(G)$ be the degree of a graph.
\item[Chromatic index] The chromatic index $\chi'(G)$ is the number of
  colors required to color each edge of the graph such that no
  adjacent edges have the same color. It is always true that the
  chromatic index $\chi'(G) = \Delta(G)$ or $\Delta(G) + 1$.
\item[Critical] A graph is $\Delta$-critical if it has
  chromatic index $\Delta + 1$ but can be $\Delta$-colored if any edge
  is removed.
\item[Overfull] A graph is overfull if it has more than
  $\Delta\lfloor\frac{\abs{V}}{2}\rfloor$ edges. Overfull graphs
  require $\Delta + 1$ colors to color, because a matching of each
  edge can have only $\lfloor\frac{\abs{V}}{2}\rfloor$ edges;
  otherwise, two adjacent edges would have the same color.
\item[2-factor] A 2-factor is an edge-disjoint decomposition of a
  graph into 2-regular subgraphs that span the vertices.
\item[Independence number] The independence number $\alpha(G)$ is the
  size of the largest set of vertices such that no edge connects any
  pair.
\end{description}


\section{Conjectures}
\label{sec:conjectures}

Two open conjectures relate to critical graphs.

\begin{enumerate}
\item Every critical graph has a 2-factor.
\item Every critical graph has independence number less than or equal
  to half the number of vertices.
\end{enumerate}

The results in this paper approximate these conjectures, when the
graphs in question have many edges.




\section{Main result}
\label{sec:mainresult}

For a graph $G=(V,E)$, let $d(v)$ be the degree of vertex $v$, and
define the slack $s(G) = \sum_{v\in V}\Delta(G) - d(v)$.

\newtheorem{paritylemma}{Lemma}
\begin{paritylemma}
  Let $\phi$ be a $\Delta$-coloring with colors
  $\{1,2,\ldots,\Delta\}$, and $a_i$ be the number of vertices where
  color $i$ is missing. Then, $\forall i \; a_i \equiv \abs{V(G)}
  \pmod{2}$.
\end{paritylemma}
\begin{proof}
  As each edge of color $i$ is added, the number of vertices where $i$
  is not present decreases by 2. So parity is maintained, mod 2.
\end{proof}

\newtheorem{mainthm}{Theorem}
\begin{mainthm}
  Let $G$ be a $\Delta$-critical graph, with $\Delta \ge 3$. Define
  $k = \min_{e=u,v}(d(u)+d(v))$. Then
  \begin{itemize}
  \item If $\abs{V}$ is odd then
    \begin{itemize}
    \item $\alpha(G) \le \frac{1}{2}(\abs{V}-3) + \lfloor
    \frac{s(G)+2k-\Delta-2}{2\Delta} \rfloor$
    \item $G$ has a 2-factor when $s(G) \le 5 \Delta -2k + 1$
    \end{itemize}
  \item If $\abs{V}$ is even then
    \begin{itemize}
    \item $\alpha(G) \le \frac{1}{2}(\abs{V}-4) + \lfloor
    \frac{s(G)+2k-2}{2\Delta} \rfloor$
    \item $G$ has a 2-factor when $s(G) \le 2 \Delta -6$
    \end{itemize}
  \end{itemize}
\end{mainthm}

\begin{proof}
  Choose an edge $e$ from $v$ to $w$ with $d(v) + d(w) = k$. After
  removing $e$, the graph is $\Delta$-colorable. $k$ must be greater
  than $\Delta + 2$. There cannot exist a color that is missing at
  both $v$ and $w$; if there were, we could color edge $e$ that color
  and thus color the entire graph with only $\Delta$ colors.

  Assume without loss of generality that the colors present at exactly
  one of $v$ and $w$ are numbered $C_1 = \{1,2,\ldots,2\Delta - k + 2\}$,
  and the colors at both are $C_2 = \{2\Delta - k + 3, \ldots,
  \Delta\}$. Let $V'$ be the set of vertices without $v$ and $w$. For
  any $i$, define $a_i'$ to be the number of vertices in $V'$ where
  color $i$ is missing. Let $a_l'$ be the minimum of the $a_i'$. Then
  there are two cases.

  \begin{enumerate}
  \item $l \in C_1$. Then
    \begin{align*}
      s(G) - 2\Delta + k &= \sum_{i=1}^\Delta a_i'\\
      &\ge a_l'\abs{C_1} + (a_l' +1)\abs{C_2} \\
      &= a_l'\Delta + k - \Delta - 2
    \end{align*}
    Thus,
    \[a_l' \le \left\lfloor\frac{S(G) + 2}{\Delta}\right\rfloor - 1\]
  \item $l \in C_2$. Then analogous argument leads to the result
    \[a_l' \le \left\lfloor \frac{s(G) + 2k -2}{\Delta}\right\rfloor
    - 4 \]
  \end{enumerate}
Since the parity lemma depends on the parity of the number of
vertices, we again consider two corresponding cases:

\begin{enumerate}
\item If \abs{V} is odd, then:
 \[a_i' \equiv
 \begin{cases} 0 \;\;& i\in C_1 \\ 1 & i\in C_2 \end{cases} \pmod{2}
 \]
 So again we must condition on whether $l$ is in $C_1$ or $C_2$:
 \begin{enumerate}
 \item If $l \in C_1$, then we suppose that $l$ is missing at $v$ and
   $m$ is missing at $w$. We observe that there is an odd circuit made
   up of alternating edges of colors $l$ and $m$, including the
   removed edge $e$ from $u$ to $v$. The proof is by contradiction: if
   no such path existed, then $G$ would not be $\Delta$-critical
   because the colors could be rearranged in such a way that color $l$
   would be missing at both vertices, and then $e$ could be colored
   $l$. Therefore, the largest independent set in $G$ can be
   $\frac{1}{2}$ of the number of vertices in this cycle minus 1. So
   $\alpha(G) \le \frac{\abs{V}+a_l'-1}{2}$. Using the bound on $a_l'$
   above, and taking into account that $a_l'$ is odd, we can improve
   the bound to
   \[\alpha(G) \le 
   \frac{1}{2} \left[ \abs{V}+ 2 \left\lfloor
       \frac{s(G)+2-\Delta}{2\Delta} \right\rfloor -1 \right] \]
 \item If $l \in C_2$, we follow the same process using instead the
   bound for $a_l'$ that corresponds to the $l \in C_2$ case. The
   result is the bound
   \[ \alpha(G) \le
   \frac{1}{2} \left[ \abs{V}+ 2 \left\lfloor
       \frac{s(G)+2k-\Delta-2}{2\Delta} \right\rfloor -3 \right] \]
 \end{enumerate}
 Next we show that $G$ has a 2-factor if $s(G) \le 5\Delta - 2k + 1$.
 In this case, $l$ must be in $C_1$. If it were in $C_2$, then the
 bound on $s(G)$ and the bound $a_l' \le \left\lfloor \frac{s(G) + 2k
     -2}{\Delta}\right\rfloor - 4$ combine to require $a_l'$ to be
 zero. But parity requires $a_l'$ to be odd. So by contradiction, $l
 \in C_1$.

 Then we consider $m \in C_1$ with $a_m' = 0$ and $m \neq l$, and
 assume without loss of generality that $l$ is not found at $v$ and
 $m$ not at $w$. Again, we consider the cycle of edges of colors $l$
 and $m$, plus the edge $e$. This and the circuits of the same colors
 of even length span $G$ and form a 2-factor.

 We note that $m$ must exist with the constraints we placed on it. If
 not, then $a_i^2 \ge 2$ for all $i \neq l \in C_1$, and using the
 same technique of counting the deficiency using the sum of the
 $a_i'$,

    \begin{align*}
      s(G) - 2\Delta + k &= \sum_{i=1}^\Delta a_i'\\
      &\ge 2(a_l'\abs{C_1} - 1) + \abs{C_2} \\
      &= 3 \Delta -k + 2 2
    \end{align*}
 which contradicts our assumption that $s(G) \le 5\Delta - 2k + 1$.


\item The case when $\abs{V}$ is even is analogous, with the bounds
  changed slightly to account for the change in parity in $\abs{V}$
  and the $a_i'$. The result is that
    \begin{enumerate}
    \item $\alpha(G) \le \frac{1}{2}(\abs{V}-4) + \lfloor
    \frac{s(G)+2k-2}{2\Delta} \rfloor$
    \item $G$ must have a 2-factor if $s(G) \le 2 \Delta -6$
    \end{enumerate}

\end{enumerate}


    
\end{proof}

\end{document}