---
abstract: 'A vertex set $D$ in a graph $G$ is *$k$-dependent* if $G[D]$ has maximum degree at most $k-1$, and *$k$-dominating* if every vertex outside $D$ has at least $k$ neighbors in $D$. Favaron proved that if $D$ is a $k$-dependent set maximizing the quantity $k{\left\lvert{D}\right\rvert} - {\left\lvert{E(G[D])}\right\rvert}$, then $D$ is $k$-dominating.  We extend this result, showing that such sets satisfy a stronger structural property, and we find a surprising connection between Favaron’s theorem and a conjecture of Tuza regarding packing and covering of triangles.' 
author:
- 'Gregory J. Puleo'
bibliography:
- 'biblio.bib'
title: 'Favaron’s Theorem, $k$-dependence, and Tuza’s Conjecture'
---

Introduction
============

A vertex set $D$ in a graph $G$ is *independent* if the induced subgraph $G[D]$ has no edges.  A vertex set is *dominating* if every vertex of $G$ either lies in the set, or has a neighbor in the set.  Ore [@Ore] observed that any maximal independent set is also a dominating set: by the maximality of the independent set, every vertex outside the set must have a neighbor in the set.  Thus, $\gamma(G) \leq {\alpha}(G)$ for any graph $G$, where $\gamma(G)$ is the size of a smallest dominating set and ${\alpha}(G)$ is the size of a largest independent set.  Fink and Jacobson [@FinkJacobson1; @FinkJacobson2] generalized the notions of independence and domination as follows. 

For positive integers $k$, a vertex set $D \subset V(G)$ is *$k$-dependent* if the induced subgraph $G[D]$ has maximum degree at most $k-1$. A vertex set $D$ is *$k$-dominating* if ${\left\lvert{N(v) \cap D}\right\rvert} \geq k$ for all $v \in V(G) - D$.

Fink and Jacobson posed the following question: letting $\gamma_k(G)$ denote the size of a smallest $k$-dominating set in $G$ and letting ${\alpha}_k(G)$ denote the size of a largest $k$-dependent set in $G$, is it true that $\gamma_k(G) \leq {\alpha}_k(G)$ for all $k$?  Setting $k=1$ yields the original inequality $\gamma(G) \leq {\alpha}(G)$. However, for $k>1$ it is no longer true that every maximal $k$-dependent set is $k$-dominating.  Favaron [@Favaron] answered the question of Fink and Jacobson, using a different notion of “optimality” for $k$-dependent sets. 

\[thm:favaron\] If $D$ is a $k$-dependent set maximizing the quantity $k{\left\lvert{D}\right\rvert} -
  {\left\lvert{E(G[D])}\right\rvert}$ (over all $k$-dependent sets), then $D$ is a $k$-dominating set. 

Since any set of at most $k$ vertices is a $k$-dependent set, it follows that every graph has a set of vertices which is both $k$-dependent and $k$-dominating, which yields $\gamma_k(G) \leq {\alpha}_k(G)$. Theorem \[thm:favaron\] motivates the following definition. 

For any set $D$, define $\phi_k(D) = k{\left\lvert{D}\right\rvert} -
  {\left\lvert{E(G[D])}\right\rvert}$. A *$k$-optimal set* is a $k$-dependent set maximizing $\phi_k$ over all $k$-dependent sets. 

The notation $\phi_k(D)$ is borrowed from the survey paper [@DomSurvey].  Notice that the maximum value of $\phi_k$ over all $k$-dependent sets is equal to the maximum value of $\phi_k$ over all vertex sets, since if $D$ is an arbitrary vertex set and $v \in D$ has degree exceeding $k-1$ in $G[D]$, then $\phi_k(D-v) \geq
\phi_k(D)$. We extend Theorem \[thm:favaron\] by proving that $k$-optimal sets satisfy a property stronger than $k$-domination. 

\[thm:main\] Let $D$ be a $k$-optimal set in a graph $G$, let $X = V(G)-D$, and let $H$ be the maximal bipartite subgraph of $G$ with partite sets $D$ and $X$. If $J$ is any orientation of $G[X]$, then $H$ has a $k$-edge-chromatic subgraph $M$ such that $d_M(v) + {d^{+}_J}(v) \geq k$ for all $v \in X$, where ${d^{+}_J}(v)$ is the outdegree of $v$ in the orientation $J$.

In particular, since we can take any vertex $v \in V(G)-D$ to have outdegree $0$ in $J$, Theorem \[thm:main\] implies that any $k$-optimal set is $k$-dominating.  In fact, we have the following stronger corollary, obtained by taking the vertices of an independent set to have outdegree $0$ in $J$.

Let $D$ be a $k$-optimal set in a graph $G$. For any independent set $S$ disjoint from $D$, there are $k$ disjoint matchings of $S$ into $D$, each saturating $S$.

We now turn to a conjecture of Tuza concerning packing and covering of triangles.  Given a graph $G$, let $\tau(G)$ denote the minimum size of an edge set $Y$ such that $G-Y$ is triangle-free, and let $\nu(G)$ denote the maximum size of a set of pairwise edge-disjoint triangles in $G$. It is easy to show that $\nu(G) \leq \tau(G) \leq 3\nu(G)$: if ${\mathcal{S}}$ is a largest set of pairwise edge-disjoint triangles, then to make $G$ triangle-free we must delete at least one edge from each triangle of ${\mathcal{S}}$, and on the other hand deleting all edges contained in triangles of ${\mathcal{S}}$ will always make $G$ triangle-free.  Tuza conjectured a stronger upper bound. 

$\tau(G) \leq 2\nu(G)$ for all graphs $G$.

Tuza’s Conjecture is sharp, if true; as observed by Tuza [@Tuza], equality in the upper bound is acheieved by any graph whose blocks are all isomorphic to $K_4$, among other examples.  The best general upper bound on $\tau(G)$ in terms of $\nu(G)$ is due to Haxell [@Haxell], who showed that $\tau(G) \leq 2.87\nu(G)$ for all graphs $G$. Tuza’s Conjecture has been studied by many authors, who proved the conjecture for special classes of graph [@SashaK4; @Krivelevich; @Puleo; @LBT; @LBT-perfect] or studied various fractional relaxations of the conjecture [@CDMMS; @HaxellRodl; @SashaStability; @Krivelevich]. 

A major theme of the author’s previous work on Tuza’s Conjecture [@Puleo] is to reduce questions about triangle packings to questions about matchings, since matchings are very well understood.  In this paper, we therefore study the conjecture on graphs of the form $I_k {\vee}H$, where $I_k$ is an independent set of size $k$, $H$ is a triangle-free graph, and the *join* $G_1 {\vee}G_2$ of two graphs $G_1$ and $G_2$ is obtained from the disjoint union of $G_1$ and $G_2$ by adding all possible edges between $V(G_1)$ and $V(G_2)$. Each triangle of $I_k {\vee}H$ consists of an edge in $H$ together with a vertex of $I$; thus, triangle packings in $I_k {\vee}H$ correspond to partial $k$-edge-colorings of $H$. The connection between Tuza’s Conjecture and Favaron’s Theorem is given by the following result. 

\[thm:tuzaconnection\] For a graph $G$ and $k \in {\mathbb{Z}}^+$, let $\phi_k(G)$ denote the maximum value of $\phi_k(D)$ over all $k$-dependent sets $D \subset
  V(G)$, and let $\alpha'_k(G)$ denote the largest number of edges in a $k$-edge-colorable subgraph of $G$. If $H$ is triangle-free, then $$\begin{aligned}
    \nu(I_k {\vee}H) &= \alpha'_k(H),\text{ and} \\
    \tau(I_k {\vee}H) &= k{\left\lvert{V(H)}\right\rvert} - \phi_k(H). 
  \end{aligned}$$

Thus, this special case of Tuza’s Conjecture can be interpreted as requesting a relationship between the $\phi_k$-value of a $k$-optimal set and the size of a largest $k$-edge-colorable subgraph of a graph.  We formalize this special case below. 

\[coj:specialtuza\] If $k \in {\mathbb{Z}}^+$ and $H$ is a triangle-free graph, then $\tau(I_k {\vee}H) \leq 2\nu(I_k {\vee}H)$. Equivalently, $\alpha'_k(H) \geq k{\left\lvert{V(H)}\right\rvert} - \phi_k(H)$.

A similar idea appears in a paper of Chapuy, DeVos, McDonald, Mohar, and Schiede [@CDMMS].  Studying a fractional version of Tuza’s conjecture, they consider a triangle-free Ramsey graph $H$ with low independence number (hence matching number close to ${\left\lvert{V(H)}\right\rvert}/2$) and use $I_1 {\vee}H$ as a sharpness example for an upper bound on $\tau(G)$.

The rest of the paper is organized as follows.  In Section \[sec:k1\] we build some intuition by exploring the $k=1$ case of Theorem \[thm:main\].  Based on a result that holds in the $k=1$ case, we pose the following conjecture, which is natural in its own right and which implies Conjecture \[coj:specialtuza\]:

\[coj:sec1deg\] If $D$ is a $k$-optimal set in a graph $G$, then $G$ has a $k$-edge-chromatic subgraph in which every vertex of $V(G)-D$ has degree $k$.

In Section \[sec:leben\] we prove a generalization of a theorem of Lebensold concerning disjoint matchings in bipartite graphs.  In Section \[sec:proof\] we apply the results of Section \[sec:leben\] to prove Theorem \[thm:main\].  In Section \[sec:tuza\] we prove Theorem \[thm:tuzaconnection\] and and show that Conjecture \[coj:sec1deg\] implies Conjecture \[coj:specialtuza\].  In Section \[sec:chordal\] we introduce the notion of *saturability*, which is a variant of list edge coloring.  We formulate a conjecture about graph decompositions and show that this conjecture implies Conjecture \[coj:sec1deg\].  The proof uses Galvin’s kernel method [@Galvin].  Finally, we apply Theorem \[thm:main\] to prove that Conjecture \[coj:sec1deg\] holds for chordal graphs. 

The $k=1$ Case of Theorem \[thm:main\] {#sec:k1}
======================================

When $k=1$, things are simpler: a $1$-dependent set is just an independent set, so a $1$-optimal set is just a maximum-size independent set.  The statement of Theorem \[thm:main\] can also be simplified: when $k=1$, the only vertices of $V(G)-D$ for which the theorem says anything are those of outdegree $0$, which form an independent set.  Thus, the $k=1$ case of Theorem \[thm:main\] is equivalent to the following proposition, which we prove using Hall’s Theorem [@HallsTheorem]:

\[prop:k1\] Let $D$ be a maximum-size independent set in a graph $G$. If $T$ is an independent set disjoint from $D$, then $G$ has a matching of $T$ into $D$ that saturates $T$.

Assume that no such matching exists; we will obtain an independent set $D'$ with ${\left\lvert{D'}\right\rvert} > {\left\lvert{D}\right\rvert}$. If no such matching exists, then by Hall’s Theorem, there is a set $S \subset T$ such that ${\left\lvert{N(S) \cap D}\right\rvert} < {\left\lvert{S}\right\rvert}$. Let $D' = (D - N(S)) \cup S$. Since $S$ and $D$ are independent and since we have deleted $N(S)$, the set $D'$ is also independent.  Since ${\left\lvert{N(S) \cap D}\right\rvert} < {\left\lvert{S}\right\rvert}$, we have ${\left\lvert{D'}\right\rvert} > {\left\lvert{D}\right\rvert}$, as desired. 

In fact, Proposition \[prop:k1\] is one half of Berge’s “Maximum Stable Set Lemma” [@Berge], which states that an independent set $D$ is maximum if and only if every independent set $T$ disjoint from $D$ matches into $D$.

The proof of Theorem \[thm:main\] uses a similar strategy to the proof of Proposition \[prop:k1\]: assuming that the desired $k$-edge-chromatic subgraph does not exist, we obtain a set of vertices for which a similar Hall-type condition fails, and we use this set of vertices to construct a “better” $k$-dependent set. 

Proposition \[prop:k1\] implies the $k=1$ case of Conjecture \[coj:sec1deg\], but we have not been able to generalize this proof to higher $k$.

\[cor:match\] If $D$ is a maximum-size independent set in a graph $G$, then $G$ has a matching that saturates every vertex of $V(G)-D$.

Let $M_1$ be a maximal matching in $V(G)-D$, and let $S$ be the set of vertices in $V(G)-D$ not saturated by $M_1$. Since $M_1$ is a maximal matching, $S$ is an independent set.  By Proposition \[prop:k1\], there is a matching $M_2$ of $S$ into $D$ that saturates $S$. Thus, $M_1 \cup M_2$ is a matching that saturates $V(G)-D$.

Since Theorem \[thm:main\] generalizes Proposition \[prop:k1\], one would hope that it could play an analogous role in a proof of Conjecture \[coj:sec1deg\], but it appears difficult to find a suitable orientation to use.  This difficulty is explored further in Section \[sec:tuza\]. 

Extending Lebensold’s Theorem {#sec:leben}
=============================

Lebensold [@Lebensold] proved the following generalization of Hall’s Theorem.  As Brualdi observed in his review of [@Lebensold], the theorem is equivalent to a theorem of Fulkerson [@Fulkerson] concerning disjoint permutations in $0,1$-matrices.  An alternative proof of the theorem, using matroid theory, is due to Murty [@Murty]. 

\[thm:leb\] An $X,D$-bigraph has $k$ disjoint matchings from $X$ into $D$, each saturating $X$, if and only if $$\sum_{v \in D}\min\{ k, {\left\lvert{N(v) \cap {S}}\right\rvert} \} \geq k{\left\lvert{{S}}\right\rvert}$$ for every subset ${S}\subset X$.

We extend the theorem to find necessary and sufficient conditions for the existence of a $k$-edge-chromatic subgraph in which the vertices of $X$ are allowed to have different degrees. 

\[lem:genleb\] Let $H$ be an $X,D$-bigraph, and write $X = \{v_1, \ldots,
  v_t\}$. Let $k$ be a positive integer and let $d_1, \ldots, d_t$ be nonnegative integers with all $d_i \leq k$. The following are equivalent:

(1) $H$ has a $k$-edge-chromatic subgraph $M$ such that $d_M(v_i) \geq d_i$ for all $i$;

(2) For every subset ${S}\subset X$, $$\sum_{v \in D}\min\{ k, {\left\lvert{N(v) \cap {S}}\right\rvert}\} \geq \sum_{v_i \in {S}}d_i.$$

Theorem \[thm:leb\] is the special case of Lemma \[lem:genleb\] obtained when all $d_i = k$. We prove Lemma \[lem:genleb\] using Theorem \[thm:leb\], so Theorem \[thm:leb\] is self-strengthening in this sense. 

For each $i$, let $D_i$ be a set of size $k-d_i$, with all sets $D_i$ disjoint from each other and disjoint from $V(H)$, and let $D'
  = D \cup D_1 \cup \cdots \cup D_t$. Let $H'$ be the $X,D'$-bigraph obtained from $H$ by making the vertices in $D_i$ adjacent only to $v_i$. Consider the following two statements:

1.   $H'$ has $k$ edge-disjoint matchings, each saturating $X$;

2.   For every subset ${S}\subset X$, $$\sum_{v \in D'}\min\{ k, {\left\lvert{N(v) \cap {S}}\right\rvert}\} \geq k{\left\lvert{{S}}\right\rvert}.$$

By Theorem \[thm:leb\], (1$'$) is equivalent to (2$'$).  We prove that (1) is equivalent to (1$'$) and (2) is equivalent to (2$'$). 

If $M_1, \ldots, M_k$ are edge-disjoint matchings in $H'$ each saturating $X$, then their restriction to $H$ yields a $k$-edge-chromatic subgraph $M$ of $H$ with each $d_M(v_i) \geq
  d_i$. Conversely, any such subgraph of $H$ can be extended to $k$ edge-disjoint matchings in $H'$. Thus, (1) is equivalent to (1$'$). 

Elements of $D_i$ each contribute $1$ to the sum in (2$'$) when $v_i \in {S}$, and contribute $0$ otherwise.  This yields $$\sum_{v \in D'}\min\{k, {\left\lvert{N(v) \cap {S}}\right\rvert}\} = \sum_{v_i \in {S}}(k - d_i) + \sum_{v \in D}\min\{k, {\left\lvert{N(v) \cap {S}}\right\rvert}\},$$ so (2) is equivalent to (2$'$). 

Proof of Theorem \[thm:main\] {#sec:proof}
=============================

The following observation was mentioned in the introduction; we repeat it here because of its central role in this section. 

\[obs:subset\] If $G$ is a graph and $T \subset V(G)$, then for any $k$, there is a $k$-dependent subset $D \subset T$ such that $\phi_k(D) \geq \phi_k(T)$.

As a consequence of Observation \[obs:subset\], in order to prove that some vertex set $D$ is not $k$-optimal, it suffices to find *any* vertex set $D'$ with $\phi_k(D') > \phi_k(D)$, without worrying about whether $D'$ is $k$-dependent.  When $k$ is a nonnegative integer, we write $[k]$ for the set $\{1, \ldots, k\}$.

We are now ready to prove Theorem \[thm:main\]. 

Let $D$ be a $k$-dependent set, let $X = V(G) - D$, and let $J$ be an orientation of $G[X]$. Assuming that there is no $k$-edge-chromatic subgraph with the desired properties, we construct a set $D'$ with $\phi_k(D') > \phi_k(D)$.

Since there is no $k$-edge-chromatic subgraph with the desired properties, applying Lemma \[lem:genleb\] with $d_i = \max\{0, k -
  {d^{+}_J}(v)\}$ shows that there is a set ${S}\subset X$ such that $$\sum_{v \in D}\min\{ k, {\left\lvert{N(v) \cap {S}}\right\rvert}\} < \sum_{v_i \in {S}}\max\{0, k-{d^{+}_J}(v)\}.$$ We may assume that ${d^{+}_J}(v) \leq k$ for all $v \in {S}$, since vertices with ${d^{+}_J}(v) > k$ may be removed from ${S}$ without causing the above inequality to fail.  This gives the simpler inequality $$\label{eq:lebfail}
    \sum_{v \in D}\min\{ k, {\left\lvert{N(v) \cap {S}}\right\rvert}\} < k{\left\lvert{{S}}\right\rvert} - \sum_{v_i \in {S}}{d^{+}_J}(v).$$ Define sets $B$ and $A$ by $$\begin{aligned}
 B &= \{v \in D {\colon\,}{\left\lvert{N(v) \cap {S}}\right\rvert} \leq k-1\}, \\
 A &= D-B, \\\end{aligned}$$ Let $D' = B \cup {S}$. We claim that $\phi_k(D') > \phi_k(D)$. First observe that $$\sum_{v \in D}\min\{ k, {\left\lvert{N(v) \cap {S}}\right\rvert}\} = k{\left\lvert{A}\right\rvert} + \sum_{v \in B}{\left\lvert{N(v) \cap {S}}\right\rvert} = k{\left\lvert{A}\right\rvert} + {\left\lvert{[{S}, B]}\right\rvert},$$ where $[{S}, B]$ is the set of all edges with one endpoint in ${S}$ and the other endpoint in $B$. Thus, from , $$\begin{aligned}
  k{\left\lvert{A}\right\rvert} + {\left\lvert{[{S}, B]}\right\rvert} &< k{\left\lvert{{S}}\right\rvert} - \sum_{v_i \in {S}}{d^{+}_J}(v)\nonumber\\
  &\leq k{\left\lvert{{S}}\right\rvert} - {\left\lvert{E(G[{S}])}\right\rvert}.\label{eq:cat}\end{aligned}$$ On the other hand, we have $$\phi_k(D') \geq \phi_k(D) - k{\left\lvert{A}\right\rvert} + k{\left\lvert{{S}}\right\rvert} - {\left\lvert{[{S}, B]}\right\rvert} - {\left\lvert{E(G[{S}])}\right\rvert}.$$ Combining this with Inequality \[eq:cat\] yields $\phi_k(D') > \phi_k(D)$, as desired.  Thus, when $D$ is $k$-optimal, a $k$-edge-chromatic subgraph with the desired properties exists. 

Tuza’s Conjecture and Conjecture \[coj:sec1deg\] {#sec:tuza}
================================================

We first prove Theorem \[thm:tuzaconnection\], which furnishes a connection between Tuza’s Conjecture and $k$-optimal sets. 

Let $G = I_k {\vee}H$. We first show that $\nu(G) = {\alpha'_k}(H)$. Let ${\mathcal{S}}$ be a maximum set of edge disjoint triangles in $G$. For each $v \in I_k$, let ${\mathcal{S}}_v = \{T \in {\mathcal{S}}{\colon\,}v \in T\}$. Since each triangle in $G$ consists of exactly one vertex of $I_k$ together with an edge in $H$, we can write ${\mathcal{S}}$ as the disjoint union ${\mathcal{S}}= \bigcup_{v \in I_k}{\mathcal{S}}_v$. Since the triangles in ${\mathcal{S}}_v$ are edge-disjoint, no two triangles in ${\mathcal{S}}_v$ can share a common vertex $w \in V(H)$: if this were the case, they would intersect in the edge $vw$. Hence the edges of ${\mathcal{S}}_v$ that lie in $H$ form a matching $M_v$ in $H$. Since the triangles in ${\mathcal{S}}$ are edge-disjoint, it follows that the matchings $M_v$ are pairwise disjoint, so $\bigcup_{v \in I_k}M_v$ is a $k$-edge-colorable subgraph of $H$ having size $\nu(G)$. Therefore, $\nu(G) \leq
  {\alpha'_k}(H)$.

On the other hand, if $H_0$ is a maximum $k$-edge-colorable subgraph of $H$, then we can write $E(H_0) = M_1 \cup \cdots \cup M_k$, where each $M_i$ is a matching.  Let $v_1, \ldots, v_k$ be the vertices of $I_k$, and for $i \in [k]$, let ${\mathcal{S}}_i = \{v_iwz {\colon\,}wz \in M_i\}$. Now $\bigcup_{i \in [k]}{\mathcal{S}}_i$ is a family of ${\alpha'_k}(H)$ pairwise edge-disjoint triangles in $G$, so $\nu(G) \geq {\alpha'_k}(H)$.

Next we show that $\tau(G) = k{\left\lvert{V(H)}\right\rvert} - \phi_k(H)$. Let $D$ be a $k$-optimal subset of $V(H)$, and define an edge set $X$ by $$X = E(D) \cup \{vw {\colon\,}\text{$v \in I_k$ and $w \in
    V(H)-D$}\}.$$ Clearly, ${\left\lvert{X}\right\rvert} = {\left\lvert{E(G[D])}\right\rvert} +
  k({\left\lvert{V(H)}\right\rvert}-{\left\lvert{D}\right\rvert})$, which rearranges to ${\left\lvert{X}\right\rvert} =
  k{\left\lvert{V(H)}\right\rvert} - \phi_k(H)$, since $D$ is $k$-optimal.  We claim that $G-X$ is triangle-free.  Let $T$ be any triangle in $G$; we may write $T=uvw$, where $uw \in E(H)$ and $v \in I_k$. If $u \notin D$, then $vu \in X$, and likewise for $w$. On the other hand, if $u,w \in D$, then $uw \in X$. Hence $G-X$ is triangle-free, so $\tau(G) \leq k{\left\lvert{V(H)}\right\rvert} - \phi_k(H)$.

Conversely, let $X$ be a minimum edge set such that $G-X$ is triangle-free.  For each $v \in I_k$, let $C_v = \{w \in V(H) {\colon\,}vw
  \notin X\}$. We transform $X$ so that all the sets $C_v$ are equal: pick $v^* \in I_k$ to minimize ${\left\lvert{C_{v^*}}\right\rvert}$, and define $X_1$ by $$X_1 = (X \cap E(H)) \cup \{vw {\colon\,}w \in C_{v^*}\}.$$ Now $G-X_1$ is triangle-free: if $vwz$ is a triangle in $G-X_1$, then $v^*wz$ is a triangle in $G-X$, contradicting the assumption that $G-X$ is triangle-free.  Furthermore, by the minimality of ${\left\lvert{C_{v^*}}\right\rvert}$, we have ${\left\lvert{X_1}\right\rvert} \leq {\left\lvert{X}\right\rvert}$.

Therefore, ${\left\lvert{X_1}\right\rvert} = {\left\lvert{X}\right\rvert} = \tau(G)$. Let $D = V(H) - C_{v^*}$. Since $G-X_1$ is triangle-free, we have $E(G[D]) \subset X_1$, and so $${\left\lvert{X_1}\right\rvert} \geq {\left\lvert{E(G[D])}\right\rvert} + k{\left\lvert{V(H) - D}\right\rvert} = k{\left\lvert{V(H)}\right\rvert} - \phi_k(D).$$ While $D$ need not be $k$-dependent, the maximum value of $\phi_k$ over subsets of $H$ is achieved at some $k$-dependent vertex set, so $\phi_k(D) \leq \phi_k(H)$. Hence, $$\tau(G) = {\left\lvert{X_1}\right\rvert} \geq k{\left\lvert{V(H)}\right\rvert} - \phi_k(H).\qedhere$$

The following lemma shows that Conjecture \[coj:sec1deg\] implies Conjecture \[coj:specialtuza\]. 

\[lem:edgetuza\] Let $D$ be a $k$-optimal set in a graph $G$. If $G$ has a $k$-edge-chromatic subgraph in which every vertex of $V(G)-D$ has degree $k$, then $$k{\left\lvert{V(G)}\right\rvert} - \phi_k(G) \leq 2{\alpha'_k}(G).$$ In particular, if $G$ is triangle-free, then $\tau(I_k {\vee}G) \leq 2\nu(I_k {\vee}G)$.

Since $\Delta(G[D]) \leq k-1$, Vizing’s Theorem [@Vizing] implies that $G[D]$ is $k$-edge-colorable.  Let $N_1, \ldots, N_k$ be the $k$ edge-disjoint matchings in a $k$-edge-coloring of $G[D]$, so that $N_1 \cup \cdots \cup N_k = E(G[D])$, and let $M'_1, \ldots, M'_k$ be $k$ pairwise edge-disjoint matchings each saturating $V(G)-D$, as guaranteed by the hypothesis.  For each $i$, let $M'_i$ be the matching defined by $$M_i = M'_i \cup \{e \in N_i {\colon\,}\text{$e \cap f = \emptyset$ for all $f \in M'_i$}\}.$$ Let $T = M_1 \cup \cdots \cup M_k$. Clearly $T$ is $k$-edge-chromatic, so ${\alpha'_k}(G) \geq {\left\lvert{T}\right\rvert}$.

A *cross-edge* is an edge of $T$ with exactly one endpoint in $D$. If there are $q$ cross-edges, then the degree-sum formula yields $$\sum_{i=1}^k {\left\lvert{M'_i}\right\rvert} = \frac{k}{2}{\left\lvert{V(G)-D}\right\rvert} + \frac{q}{2}.$$ Furthermore, if there are $r$ edges of $G[D]$ which fail to appear in $T$, then each of these edges is “witnessed” by a different cross-edge, so $r \leq q$. Clearly $r \leq {\left\lvert{E(G[D])}\right\rvert}$, so $$\begin{aligned}
    \sum_{i=1}^k {\left\lvert{M_i}\right\rvert} &= \frac{k}{2}{\left\lvert{V(G) - D}\right\rvert} + \frac{q}{2} + {\left\lvert{E(G[D])}\right\rvert} - r \\
    &\geq \frac{k}{2}{\left\lvert{V(G) - D}\right\rvert} + {\left\lvert{E(G[D])}\right\rvert} - \frac{r}{2} \\
    &\geq \frac{k}{2}{\left\lvert{V(G) - D}\right\rvert} + \frac{1}{2}{\left\lvert{E(G[D])}\right\rvert}. 
  \end{aligned}$$ It follows that $$2{\alpha'_k}(G) \geq 2{\left\lvert{T}\right\rvert} \geq k{\left\lvert{V(G)-D}\right\rvert} + {\left\lvert{E(G[D])}\right\rvert} = k{\left\lvert{V(G)}\right\rvert} - \phi_k(G).  \qedhere$$

Conjecture \[coj:sec1deg\] implies Conjecture \[coj:specialtuza\]. 

The proof technique of Lemma \[lem:edgetuza\] *almost* yields an inductive proof of Conjecture \[coj:sec1deg\], in the following sense. 

Let $D$ be a $k$-optimal set of a graph $G$, let $X = V(G)-D$, and let $G' = G[X]$. Suppose that Conjecture \[coj:sec1deg\] holds for $G'$, let $D'$ be a $k$-optimal set in $G[X]$, and let $M'_1, \ldots, M'_k$ be $k$ disjoint matchings in $G'$, each saturating $X-D'$.

Let $N_1,\ldots,N_k$ be the matchings of a $k$-edge-coloring of $G[D]$, and use $N_1,\ldots,N_k$ and $M'_1,\ldots,M'_k$ to form a $k$-edge-chromatic subgraph $T'$ in $G'$ by the same method used in the proof of Lemma \[lem:edgetuza\].  Now for each edge $uv$ of $G[D']$ that fails to lie in $T'$, we have $uv \in N_i$ for some $i$, and without loss of generality, the endpoint $u$ is covered by $M'_i$. Orient $uv$ from $u$ to $v$. (If both endpoints are covered by $M'_i$, we may orient $uv$ either way.)  Let $J$ be the resulting orientation of $G[D']$.

Observe that each vertex $v \in D'$ is incident to ${d^{+}_J}(v)$ edges of the $k$-edge-chromatic graph $T'$. Since $D$ is $k$-optimal in $G$, it is $k$-optimal in $G[D \cup D']$. Now by Theorem \[thm:main\], there is another $k$-edge-chromatic graph $M$ with $E(M) \subset [D, D']$ such that $d_M(v) + {d^{+}_J}(v) \geq k$ for each $v \in D'$. Thus $M \cup T'$ is a subgraph of $G$ where all vertices outside $D$ have degree at least $k$; indeed, $M \cup T'$ can be taken so that the vertices outside $D$ have degree exactly $k$ and the vertices of $D'$ have degree at most $k$. The problem is that $M \cup T'$ need not be $k$-edge-chromatic, even though $M$ and $T'$ are $k$-edge-chromatic.  In other words, we cannot guarantee that the “received coloring” of $M$ agrees with the received coloring of $T'$.

A Graph Decomposition Conjecture {#sec:chordal}
================================

In this section, we introduce a conjecture concerning graph decomposition which implies Conjecture \[coj:sec1deg\] (and therefore Conjecture \[coj:specialtuza\]). 

A *sequential decomposition* of a digraph $J$ is a sequence $H_1, H_2, \ldots$ of spanning subdigraphs of $J$ such that each arc of $J$ belongs to exactly one $H_i$.

The only difference between a sequential decomposition and a decomposition in the usual sense is that a sequential decomposition has an explicit order on the subdigraphs, whereas a classical decomposition is an unordered collection of subdigraphs whose edges partition $E(J)$.

\[coj:decomp\] For every graph $G$, there is an orientation $J$ having no directed odd cycle and admitting a sequential decomposition $H_1, H_2, \ldots$ such that:

-   Each component of $H_i$ is a directed path or directed even cycle, and

-   For each $v \in V(J)$ and each $i$, we have ${d^+}_{H_i}(v) \geq {d^+}_{H_{i+1}}(v)$.

We call a sequential decomposition of the form requested by Conjecture \[coj:decomp\] a *good decomposition* of $J$. In the rest of this section, we prove that Conjecture \[coj:decomp\] implies Conjecture \[coj:sec1deg\], and we prove Conjecture \[coj:decomp\] for chordal graphs, which implies the following special case of Conjecture \[coj:sec1deg\]. 

\[thm:chordal\] If $D$ is a $k$-optimal set in a chordal graph $G$, then $G$ has a $k$-edge-chromatic subgraph in which every vertex of $V(G)-D$ has degree $k$.

The proof requires some new definitions.  Our main definition is a variant on list coloring.  While the concept of a list assignment is well-studied in other contexts, the concept of an ${\ell}$-saturating partial edge coloring for a list assignment is, to our knowledge, new. ( Typically, list assignments are used in vertex coloring problems, and represent the colors available at a vertex.) 

\[def:saturate\] A *list assignment* on a graph $G$ is a function ${\ell}$ that assigns to each vertex $v$ a set of colors ${\ell}(v)$. A (proper) partial edge coloring is *${\ell}$-saturating* if for every vertex $v$ and every color $c \in {\ell}(v)$, some edge incident to $v$ receives the color $c$. A graph $G$ is *${\ell}$-saturable* if it has an ${\ell}$-saturating partial edge coloring.  When $f$ is a function from $V(G)$ into the nonnegative integers, we say that $G$ is *$f$-saturable* if $G$ is ${\ell}$-saturable whenever ${\left\lvert{{\ell}(v)}\right\rvert}
  \leq f(v)$ for all $v$.

The connection between Conjecture \[coj:sec1deg\] and Definition \[def:saturate\] is given by the following lemma. 

\[lem:satur\] Let $D$ be a $k$-optimal set in a graph $G$, and let $X =
  V(G)-D$. If $G[X]$ has some orientation $J$ such that $G[X]$ is ${d^{+}_J}$-saturable, then $G$ has a $k$-edge-chromatic subgraph in which all vertices of $X$ have degree $k$.

Let $J$ be any such orientation of $X$, and let $M'$ be the $k$-edge-chromatic subgraph given by Theorem \[thm:main\].  Write $M' = M'_1 \cup \cdots \cup M'_k$, where each $M_i$ is a matching, and for each $v \in X$, let ${\ell}(v)$ be the set of all indices $i \in [k]$ such that $v$ is not saturated by $M'_i$. The degree condition on $M'$ yields ${\left\lvert{{\ell}(v)}\right\rvert} = \min\{{d^{+}_J}(v), k\}$.

Since $G[X]$ is ${d^{+}_J}$-saturable, there is a partial edge coloring $\psi$ of $G[X]$ that is ${\ell}$-saturating.  For $i \in [k]$, let $M^*_i$ be the set of edges that receive color $i$ in $\psi$. Now we combine the matchings $M_1, \ldots, M_k$ with the matchings $M^*_1, \ldots, M^*_k$. For each $i \in [k]$, let $M_i$ be the set defined by $$M_i = M^*_i \cup \{e \in M'_i {\colon\,}\text{$e \cap e^* = \emptyset$
    for all $e^* \in M^*_i$}\}.$$ By construction, each edge set $M_i$ is a matching.  Furthermore, every vertex of $v$ is incident to an edge in each $M_i$, since if $v$ is not incident to any edge of $M'_i$, then $i \in L(v)$, so that $v$ is incident to an edge in $M^*_i$. Thus, the $k$-edge-chromatic subgraph $M_1 \cup \cdots \cup
  M_k$ has the desired properties. 

\[lem:decomp-sat\] Let $J$ be an orientation of a graph $G$. If $J$ admits a good decomposition, then $G$ is ${d^{+}_J}$-saturable. 

The proof of Lemma \[lem:decomp-sat\] uses Galvin’s kernel method; we reproduce the relevant definitions and lemmas here.  The proof uses Galvin’s kernel method [@Galvin], and we reproduce the relevant definitions and lemmas here. 

A *kernel* of a digraph $D$ is an independent set $S$ such that for every $v \in D-S$, there is some $w \in S$ with $vw \in E(D)$. A digraph is *kernel-perfect* if every induced subgraph has a kernel. 

If ${\ell}$ is a list assignment on $G$, a *proper ${\ell}$-coloring* of $G$ is a proper coloring $\phi$ of $G$ such that $\psi(v) \in
  {\ell}(v)$ for all $v \in V(G)$. If $f$ is a function from $V(G)$ into the nonnegative integers, we say that $G$ is *$f$-choosable* if: for every list assignment ${\ell}$ with ${\left\lvert{{\ell}(v)}\right\rvert} \geq f(v)$ for all $v \in V(G)$, there is a proper ${\ell}$-coloring of $G$.

List colorings were first studied by Erdős, Rubin, and Taylor [@ERT] and by Vizing [@Vizing76]. 

\[lem:BBS\] If $D$ is a kernel-perfect orientation of a graph $G$ and $f(v) = 1+d_D^+(v)$ for all $v \in V(G)$, then $G$ is $f$-choosable. 

\[lem:galvin\] Let $H$ be a line graph of an $(X,Y)$-bigraph $U$, and let $\phi$ be an integer-valued proper edge coloring of $U$. Define an orientation of $H$ as follows: for $e_1e_2 \in E(H)$ with $\phi(e_1) < \phi(e_2)$, orient the edge $e_1e_2$ from $e_1$ to $e_2$ if their common endpoint lies in $X$, and orient the edge from $e_2$ to $e_1$ if their common endpoint lies in $Y$. The resulting orientation is kernel-perfect. 

Define an auxiliary bipartite graph $U$ as follows.  Let $X$ and $Y$ be disjoint copies of $V(G)$, and for each $v \in V(G)$, let $v_x$ and $v_y$ denote the copies of $v$ in $X$ and $Y$ respectively.  Define $$\begin{aligned}
    V(U) &= X \cup Y, \\
    E(U) &= \{u_xv_y {\colon\,}(u,v) \in E(J)\}. 
  \end{aligned}$$ Define an edge-coloring $\phi$ of $U$ as follows: for every arc $(u,v) \in J$, let $\phi(u_xv_y)$ be the unique index $i$ such that $(u,v) \in E(H_i)$. Observe that $\phi$ is a proper edge-coloring of $U$, since for each $i$, every vertex has maximum indegree and maximum outdegree at most $1$ in $H_i$. Furthermore, for every $u_x \in X$, the colors on edges incident to $u_x$ are precisely the colors $\{1, \ldots, d(u_x)\}$, since if $u_x$ lacks an incident edge of color $i$, then ${d^+}_{H_i}(u) = 0$, which implies ${d^+}_{H_j}(u) = 0$ for all $j > i$, so that $u_x$ has no incident edge of color $j$ for any $j > i$.

Let $Z$ be the kernel-perfect orientation of $L(U)$ obtained from Lemma \[lem:galvin\].  We claim that every edge $u_xv_y \in E(U)$ has degree at most $d_U(u_x)-1$ in $Z$. To see this, let $e$ be an out-neighbor of $u_xv_y$ in $Z$, and let $w$ be the common endpoint of $e$ and $u_xv_y$. If $w = u_x$, then $\phi(u_xv_y) < \phi(e) \leq d_U(u_x)$, while if $w = v_y$, then $1 \leq \phi(e) < \phi(u_xv_y)$. As $\phi$ is a proper edge-coloring, this implies that there are at most $d_U(u_x) - 1$ out-neighbors of $u_xv_y$.

By Lemma \[lem:BBS\], it follows that $L(U)$ is $f$-choosable, where $f(u_xv_y) = {d^{+}_J}(u_x)$ for all $u_xv_y \in E(U)$. Now we show that $G$ is ${d^{+}_J}$-saturable.  Let ${\ell}$ be any list assignment on $G$ with ${\left\lvert{{\ell}(v)}\right\rvert} \leq {d^{+}_J}(v)$ for all $v$. By adding extra colors if necessary, we may assume that ${\left\lvert{{\ell}(v)}\right\rvert} = {d^{+}_J}(v)$ for all $v$. Define a list assignment ${\ell}'$ on $L(U)$ as follows: for each edge $u_xv_y \in E(U)$, let ${\ell}'(u_xv_y) = {\ell}(u_x)$. Since $L(U)$ is $f$-choosable, there is a proper ${\ell}'$-coloring $\psi$ of $L(U)$.

Observe that for each vertex $u \in V(G)$, we have $d_Z(u_x) = {d^{+}_J}(u)$, and that all edges incident to $u_x$ in $Z$ have the list ${\ell}(u)$ with size ${d^{+}_J}(u)$. Thus, for each color $c \in {\ell}(u)$, the vertex $u_x$ is incident to exactly one edge $e$ with $\psi(e) = c$.

Now for any color $c$ used in $\psi$, let $U_c$ be the subgraph of $Z$ consisting of the edges of color $c$, and let $J_c$ be the spanning subdigraph of $J$ with arc set $\{(u,v) {\colon\,}u_xv_y \in U_c$. Since $\psi$ is a proper edge-coloring of $Z$, we see that $U_c$ is a matching, which implies that $J_c$ has maximum indegree and maximum outdegree at most $1$. Since $J$ has no odd cycles, every component of $J_c$ is a directed path (possibly a $1$-vertex path) or a directed even cycle.  Either way, there is a matching $M_c$ in the underlying graph of $J_c$ that covers every vertex with positive outdegree in $J_c$.

Now we obtain a partial edge-coloring $\xi$ of $G$ by coloring the edges in $M_c$ with color $c$, for each color $c$ used in $\psi$. Since each $M_c$ is a matching, the partial edge-coloring is clearly proper.  Furthermore, if $c \in {\ell}(u)$ for $u \in V(G)$, then $u_x$ is incident to some edge $e$ with $\psi(e)=c$, so $u$ has positive outdegree in $J_c$, and therefore is covered by $M_c$. It follows that $\xi$ is ${\ell}$-saturating.  As ${\ell}$ was arbitrary, $G$ is ${d^{+}_J}$-saturable. 

We prove Theorem \[thm:chordal\] via the following lemma.  A *simplicial elimination order* is a vertex ordering ${\mathord{<}}$ such that when the vertices of $G$ are written $v_1, \ldots, v_n$ in order according to ${\mathord{<}}$, then for each $i$, the neighborhood of $v_i$ in the graph $G - \{v_1, \ldots, v_{i-1}\}$ is a clique.  A graph is chordal if and only if it has a simplicial elimination order [@Chordal]. 

\[lem:simp\] Let ${\mathord{<}}$ be a simplicial elimination ordering on an $n$-vertex graph $G$. If $J$ is the orientation of $G$ obtained by orienting each edge $uv$ with $u < v$ from $v$ to $u$, then $G$ is ${d^{+}_J}$-saturable. 

We use induction on $n$. When $n=1$, there is nothing to prove, so assume that $n > 1$ and the claim holds for smaller $n$. Let ${\mathord{<}}$ be a simplicial elimination order on $G$ and let ${\ell}$ be a list assignment with ${\left\lvert{{\ell}(v)}\right\rvert} = {d^{+}_J}(v)$ for all $v$.

Let $v$ be the minimum vertex in ${\mathord{<}}$, and let $w_1 < \ldots < w_t$ be the neighbors of $v$, written in order according to ${\mathord{<}}$. Because $N(v)$ is a clique, we have ${d^{+}_J}(w_i) \geq i$ for each $i \in [t]$, since $w_i$ has, as smaller neighbors, at least $v$ and $w_1,
  \ldots, w_{i-1}$. Thus, we may choose distinct colors $c_1, \ldots,
  c_t$ such that $c_i \in {\ell}(w_i)$ for each $i$.

Let $G' = G-v$ and let $J' = J-v$. Since the restriction of ${\mathord{<}}$ to $G'$ is still a simplicial elimination order, and since $J'$ is obtained from ${\mathord{<}}$ in the prescribed manner, the induction hypothesis says that $G'$ is ${d^{+}_{J'}}$-saturable, where ${d^{+}_{J'}}(w)$ is the downdegree of $w$ in $J'$. Furthermore, for all $w \in V(G')$, we have $${d^{+}_{J'}}(w) =
  \begin{cases}
    {d^{+}_J}(w) - 1, & \text{if $w \in N(v)$;} \\
    {d^{+}_J}(w), & \text{otherwise.} 
  \end{cases}$$ Let ${\ell}'$ be the list assignment on $G'$ given by $${\ell}'(w) = 
  \begin{cases}
    {\ell}(w) - c_i, & \text{if $w = w_i$,} \\
    {\ell}(w), &\text{if $w \notin N(v)$.}
  \end{cases}$$ Now ${\left\lvert{{\ell}'(w)}\right\rvert} = {d^{+}_{J'}}(w)$ for all $w \in V(G)$, so by the induction hypothesis, $G'$ has a partial edge coloring $\psi'$ that is ${\ell}'$-down-saturating. 

The partial coloring $\psi'$ is almost ${\ell}$-saturating in $G$, except that each vertex $w_i$ may fail to have $c_i$ on an incident edge. ( As $v$ has outdegree $0$ in $J$, it makes no demands of the coloring.)  We extend $\psi'$ to a partial edge coloring of $G$ by coloring each edge $vw_i$ with color $c_i$ if $w_i$ does not yet have an incident edge of color $c_i$. Since the colors $c_i$ are distinct, the resulting partial edge coloring $\psi$ is still proper; thus, $\psi$ is ${\ell}$-saturating.  Since ${\ell}$ was arbitrary, it follows that $G$ is ${d^{+}_J}$-saturable. 

Theorem \[thm:chordal\] follows immediately from Lemma \[lem:simp\] and Lemma \[lem:satur\]: if $D$ is a $k$-optimal set in a chordal graph $G$, then the induced subgraph $G[V(G)-D]$ is again chordal, so Lemma \[lem:simp\] implies that $G$ satisfies the hypothesis of Lemma \[lem:satur\].