On $\chi$-Diperfect Digraphs with Stability Number Two

Abstract

Let D be a digraph. A proper coloring $\mathcal {C}$ and a path P of D are orthogonal if P contains exactly one vertex of each color class in $\mathcal {C}$. In 1982, Berge defined the class of $\chi$-diperfect digraphs. A digraph D is $\chi$-diperfect if for every minimum coloring $\mathcal {C}$ of D, there exists a path P orthogonal to $\mathcal {C}$ and this property holds for every induced subdigraph of D. Berge showed that some super-orientations of an odd cycle of length at least five and of its complement are not $\chi$-diperfect. In 2022, de Paula Silva, Nunes da Silva and Lee characterized which super-orientations of such graphs are $\chi$-diperfect. In this paper, we show that there are other minimal non-$\chi$-diperfect digraphs with stability number two and three. In particular, the underlying graph of these digraphs with stability number two that we have found are subgraphs of the complement of an odd cycle with at least seven vertices. Motivated by this fact, we introduce a class of graphs, called nice graphs, which consist of all 2-connected graphs in which every odd cycle has length exactly five. We characterize which super-orientations of the complement of a nice graph are $\chi$-diperfect.

Supported by CAPES - Finance Code 001, FAPESP Proc. 2020/06116-4 and 2015/11937-9, and CNPq Proc. 303766/2018-2 and Proc 425340/2016-3.

1 Introduction

Let $G=(V(G), E(G))$ be a graph. We use the concepts of path and cycle as defined in [2]. We may think of a path or cycle as a subgraph of G. The length of a path (respectively, cycle) is its number of edges. The order of a path P, denoted by |P|, defined as its number of vertices, that is, $|P| = |V(P)|$. Similarly, the order of a cycle is its number of vertices. Let $C_k$ denote the graph isomorphic to a cycle of length $k\ge 3$ and let $\overline{G}$ denote the complement of G.

We also use the concepts of stable set and clique as defined in [2]. The stability number of G is the cardinality of a maximum stable set, denoted by $\alpha (G)$. The cardinality of a maximum clique is denoted by $\omega (G)$.

A (proper) coloring $\mathcal {C}= \{C_{1}, C_{2}, ..., C_{m}\}$ of a graph G is a partition of V(G) into stable sets, also called color classes. A coloring $\mathcal {C}$ of G is minimum if $\mathcal {C}$ has the smallest possible number of color classes. The cardinality of a minimum coloring, denoted by $\chi {(G)}$, is the chromatic number of G.

For every concept for graphs, we may have an analogue for digraphs. Let $D=(V(D), A(D))$ be a digraph. The underlying graph of D, denoted by U(D), is the simple graph with vertex set V(D) such that u and v are adjacent in U(D) if and only if either $(u, v) \in A(D)$ or $(v, u) \in A(D)$ or both. We borrow terminology from undirected graphs when dealing with a digraph D by considering its underlying graph U(D). In particular, a coloring of a digraph D is a coloring of its underlying graph U(D). Similarly, we may obtain a directed graph D from a graph G by replacing each edge uv of G by an arc (u, v), or an arc (v, u), or both; such directed graph D is called a super-orientation of G. A super-orientation which does not contain a digon (a directed cycle of length two) is an orientation. A digraph D is symmetric if D is a super-orientation of a graph G in which every edge uv of G is replaced by both arcs (u, v) and (v, u).

If (u, v) is an arc of D, then we say that u dominates v and v is dominated by u. If v is not dominated by any of its neighbors, then we say that v is a source. Similarly, if v does not dominate any of its neighbors in D, then we say that v is a sink. A directed path or directed cycle is an orientation of a path or cycle, respectively, in which each vertex dominates its successor in the sequence.

Henceforth, when we say path of a digraph, we mean directed path but we will not use the same convention for cycles. When we say a cycle of a digraph, we mean either a super-orientation of an undirected cycle with length at least three or a digon. We denote by $\lambda (G)$ ($\lambda (D)$) the cardinality of a maximum path in a graph (digraph). A path in a graph or digraph is hamiltonian if it contains all of its vertices. In 1934, Rédei [10] proved the following classical result.

Theorem 1

(Rédei [10]). Every super-orientation of a complete graph has a hamiltonian path.

A graph G is perfect if $\chi (H) = \omega (H)$ for every induced subgraph H of G. It is easy to show that if G is perfect, then G cannot contain either an odd cycle of order at least five or its complement as an induced subgraph. Berge [3] conjectured that the converse was true as well. In 2006, Chudnovsky, Robertson, Seymour and Thomas [3] proved this long standing open conjecture and it became known as the Strong Perfect Graph Theorem:

Theorem 2

(Chudnovsky et al. [3]). A graph G is perfect if and only if G does not contain an odd cycle with five or more vertices or its complement as an induced subgraph.

In 1982, Berge [1] introduced the concept of $\chi$-diperfection of digraphs. Analogously to Theorem 2, he was interested in obtaining a characterization of such digraphs in terms of forbidden subdigraphs. Let $\mathcal {C}$ be a coloring and let P be a path of D. We say that $\mathcal {C}$ and P are orthogonal if $|V(P) \cap C| = 1$ for every $C\in \mathcal {C}$. We also say that $\mathcal {C}$ is orthogonal to P and vice versa. A digraph D is $\chi$-diperfect if every induced subdigraph H of D has the following property: for every minimum coloring $\mathcal {C}$ of H, there exists a path P of H such that $\mathcal {C}$ and P are orthogonal. A digraph D is diperfect if U(D) is perfect. Berge [1] showed that diperfect digraphs and symmetric digraphs are $\chi$-diperfect. For ease of further references, let us state the following.

Theorem 3

(Berge [1]). Let D be a diperfect digraph. Then, D is $\chi$-diperfect.

Berge also showed that for a cycle of length five and for the complement of an odd cycle with at least five vertices, there are orientations which are not $\chi$-diperfect. In [9], de Paula Silva, Nunes da Silva and Lee present a characterization of super-orientations of odd cycles (Theorem 4) and a characterization of super-orientations of complements of odd cycles that are $\chi$-diperfect (Theorem 5). Let D be a super-orientation of an odd cycle $C=(x_1,x_2,\ldots ,x_{2\ell +1},x_1)$ of order at least five. Let $P=(x_i,\ldots ,x_j)$ be a subpath of C. We say that the subdigraph D[V(P)] is a sector if each of $x_i$ and $x_j$ is a source or a sink in D; we say that the sector is odd if P has odd length, otherwise it is even. We also use $(x_i,\ldots ,x_j)$ or $x_iCx_j$ to denote the corresponding sector in D. We say that D is a conflicting odd cycle if it contains at least two arc-disjoint odd sectors.

Theorem 4

(de Paula Silva et al. [9]). Let D be a super-orientation of an odd cycle with order at least five. Then, D is $\chi$-diperfect if and only if D is not a conflicting odd cycle.

Theorem 5

(de Paula Silva et al. [9]). Let D be a super-orientation of the complement of an odd cycle with order at least five. Then, D is $\chi$-diperfect if and only if every vertex of D belongs to a path of order $\chi (D)$.

We say that a digraph D is an obstruction if D a minimal non-$\chi$-diperfect digraph, i.e., D is non-$\chi$-diperfect but every proper induced subdigraph of D is $\chi$-diperfect. Conflicting odd cycles and non-$\chi$-diperfect super-orientations of complements of odd cycles are examples of obstructions. Given the Strong Perfect Graph Theorem and Theorems 4 and 5, it may be tempting to conjecture that the set of obstructions is exactly the set of non-$\chi$-diperfect super-orientations of odd cycles and their complements. Investigating this question we found new obstructions with stability number two and three. In this paper, we focus on those with stability number two. Curiously, we noted that the underlying graph of such obstructions that we have found so far are spanning $(k+1)$-chromatic subgraphs of a $\overline{C_{2k+1}}$ with $k\ge 3$. Later we found out that we may build an obstruction by deleting an arc from some non-$\chi$-diperfect super-orientation of a $\overline{C_{2k+1}}$ with $k\ge 3$.

Motivated by these observations, we decided to investigate digraphs with stability number two whose underlying graph does not contain spanning $(k+1)$-chromatic subgraphs of a $\overline{C_{2k+1}}$ with $k\ge 3$. In other words, we are interested in a family $\mathcal {H}$ of digraphs in which $D \in \mathcal {H}$ if and only if $\alpha (D)=2$ and, for every induced subdigraph $D'$ of D, it follows that $U(D')$ is not a spanning $(k+1)$-chromatic subgraph of a $\overline{C_{2k+1}}$ with $k\ge 3$. One may note that this is equivalent to saying that a digraph $D \in \mathcal {H}$ if and only if every odd cycle of $\overline{U(D)}$ has length five.

2 Related Results

In this section we present some results related to the problem we study in this paper. The first theorem we present was proved independently by Roy in 1967 [11] and Gallai in 1968 [5].

Theorem 6

(Gallai-Roy [5, 11]). Let D be a digraph. For every maximum path P of D, there is a coloring $\mathcal {C}$ of D such that P and $\mathcal {C}$ are orthogonal. In particular, $\chi (D) \le \lambda (D)$.

We may compare this with the definition of $\chi$-diperfection. In a $\chi$-diperfect digraph, we require that for every minimum coloring $\mathcal {C}$, there exists a path P such that $\mathcal {C}$ and P are orthogonal. It is known that this property does not hold for every digraph [1].

A path partition of D is a collection of vertex-disjoint paths of D that cover V(D). Let $\pi (D)$ denote the cardinality of a smallest path partition of D. We use the terms initial vertex and terminal vertex for paths to indicate the first and the last vertex in the sequence of a given path. We denote by ter(P) (respectively, ini(P)) the terminal (respectively, initial) vertex of a path P. Similarly, if $\mathcal {P}$ is a collection of paths, we denote by $ter(\mathcal {P})$ ($ini(\mathcal {P})$) the set of terminal (respectively, initial) vertices of each path in $\mathcal {P}$. A stable set S and a path partition $\mathcal {P}$ are orthogonal if $|S\cap P|=1$ for every $P\in \mathcal {P}$.

Theorem 6 has a dual version in which we exchange the roles of stable sets and paths. This result is the celebrated Gallai-Milgram’s Theorem which follows from the next lemma.

Lemma 1

(Gallai-Milgram [6]). Let D be a digraph and let $\mathcal {P}$ be a path partition of D. Then,

(i):

there is a path partition $\mathcal {Q}$ of D such that $\text {ini}(\mathcal {Q})\subset \text {ini}(\mathcal {P})$, $\text {ter}(\mathcal {Q})\subset \text {ter}(\mathcal {P})$ and $|\mathcal {Q}|=|\mathcal {P}|-1$, or

(ii):

there is a stable set S which is orthogonal to $\mathcal {P}$.

Theorem 7

(Gallai and Milgram [6]). Let D be a digraph. For every minimum path partition $\mathcal {P}$ of D, there is a stable set S such that $\mathcal {P}$ and S are orthogonal. In particular, $\pi (D) \le \alpha (D)$.

For the sake of conciseness, we refer the interested reader to Berge’s paper [1] and Sambinelli’s PhD thesis [12] for a survey of the known results on this subject.

3 Properties of Obstructions

Let D be a digraph with a fixed minimum coloring $\mathcal {S}$. We say that a subdigraph H of D is rainbow if no two vertices in H are in the same color class of $\mathcal {S}$. Similarly, a path P (respectively, cycle) in D is a rainbow path (respectively, rainbow cycle) if no two vertices in P are in the same color class of $\mathcal {S}$; moreover, if $|P|=k$, then we may say that P is a k-rainbow path. Let $D_1$ and $D_2$ be two disjoint rainbow subdigraphs of D. We say that $D_1$ and $D_2$ are color-compatible if $D_1 \cup D_2$ contains exactly one vertex of each color class of $\mathcal {S}$, i.e., $D_1 \cup D_2$ is a rainbow subdigraph of D with exactly $\chi (D)$ vertices. We also say that $D_1$ is color-compatible with $D_2$ and vice versa. A graph G is (vertex) color-critical if $\chi (G - X) < \chi (G)$ for every non-empty $X \subseteq V(G)$. Equivalently, color-critical graphs may be characterized in the following way.

Theorem 8

A graph G is color-critical if and only if for every $v \in V(G)$ there is a minimum coloring of G in which v belongs to a singleton color class.    $\blacksquare$

Now we present the relation between color-critical graphs and $\chi$-diperfection.

Lemma 2

If G is the underlying graph of an obstruction, then G is color-critical.

Proof

Towards a contradiction, suppose that G is not color-critical. Let D be a minimal non-$\chi$-diperfect super-orientation of G. Let $\mathcal {S}$ be a minimum coloring of D that does not admit a $\chi (D)$-rainbow path. Let $D'$ be a proper subdigraph of D such that $\chi (D) = \chi (D')$. Clearly, $\mathcal {S}$ restricted to $D'$ is a $\chi (D')$-coloring of $D'$. Since D is a minimal non-$\chi$-diperfect digraph, there is a $\chi (D')$-rainbow path in $D'$. However, a $\chi (D')$-rainbow path of $D'$ is also a $\chi (D)$-rainbow path of D, a contradiction.    $\blacksquare$

Let D be a digraph and let $G = U(D)$. We now look at $\overline{G}$. If such graph is disconnected, it is easy to see that G can be partitioned into two disjoint subgraphs, say $G_1$ and $G_2$, such that every vertex of $G_1$ is adjacent to every vertex of $G_2$. So in any coloring of $\mathcal {S}$ of G, no color class of $\mathcal {S}$ contains vertices of both $G_1$ and $G_2$. Based on this fact, we show in Lemma 4 that $\overline{G}$ must be 2-connected when D is an obstruction. Before we state such result, we need to present a lemma that is a straightforward application of Lemma 1 but it is also useful in other places of the text.

Lemma 3

Let D be a digraph and let $P_1$ and $P_2$ be two disjoint paths of D. If every vertex of $P_1$ is adjacent to every vertex of $P_2$, then D has a path P such that (i) $V(P) = V(P_1) \cup V(P_2)$, (ii) $ini(P) \in \{ ini(P_1), ini(P_2)\}$ and (iii) $ter(P) \in \{ ter(P_1), ter(P_2)\}$.

Proof

Let $D' = D[V(P_1)\cup V(P_2)]$ and let $\mathcal {P}= \{P_1, P_2\}$ be a path partition of $D'$. Since every vertex of $P_1$ is adjacent to every vertex of $P_2$, there is no stable set orthogonal to $\mathcal {P}$. By Lemma 1, $D'$ has a path partition $\mathcal {P}'$ such that $|\mathcal {P}'| = |\mathcal {P}| - 1 = 1$, $ini(\mathcal {P}')\subset ini(\mathcal {P})$ and $ter(\mathcal {P}')\subset ter(\mathcal {P})$. Hence, the path P of $\mathcal {P}'$ satisfies properties (i)–(iii).    $\blacksquare$

Lemma 4

If G is the underlying graph of an obstruction, then $\overline{G}$ is 2-connected.

Proof

Let D be an obstruction and let $\mathcal {S}$ be a minimum coloring of D that does not admit a $\chi (D)$-rainbow path. Let $F = \overline{G}$ where G is the underlying graph of D. Towards a contradiction, suppose that F is not 2-connected. Suppose first that F is disconnected. Let X be the vertex set of a component of F and let $Y = V(F) - X$. Note that, in D, every vertex of X is adjacent to every vertex of Y. Thus, no color class of $\mathcal {S}$ has vertices in both X and Y. Moreover, $\mathcal {S}$ restricted to X and $\mathcal {S}$ restricted to Y are minimum colorings of D[X] and D[Y], respectively. Since D is a minimal non-$\chi$-diperfect digraph, there is a $\chi (D[X])$-rainbow path $P_1$ in D[X] and a $\chi (D[Y])$-rainbow path $P_2$ in D[Y]. Since $P_1$ and $P_2$ are color-compatible paths and every vertex of $P_1$ is adjacent to every vertex of $P_2$, we may apply Lemma 3 to $P_1$ and $P_2$ and obtain a $\chi (D)$-rainbow path of D, a contradiction.

So we may assume that F is connected but has a cut vertex v. Let X be the vertex set of a component of $F - v$ and let $Y = V(F) \setminus (X \cup \{v\})$. Similarly to the previous case, in D, every vertex of X is adjacent to every vertex of Y. Without loss of generality, we may assume that, if there are other vertices in the same color class of v, those vertices belong to X. Hence, no color class of $\mathcal {S}$ has vertices in both $X \cup \{v\}$ and Y. Moreover, $\mathcal {S}$ restricted to $X \cup \{v\}$ and $\mathcal {S}$ restricted to Y are minimum colorings of $D[X\cup \{v\}]$ and D[Y], respectively. Let $k = \chi (D[X\cup \{v\}])$ and $\ell = \chi (D[Y])$ (so, $\chi (D) = k + \ell$). Since D is a minimal non-$\chi$-diperfect digraph, there is a k-rainbow path in $D[X\cup \{v\}]$ and an $\ell$-rainbow path $P_2$ in D[Y]. First assume that there is a k-rainbow path $P_1$ in $D[X\cup \{v\}]$ such that $v \notin V(P_1)$. Similarly to the previous case, $P_1$ and $P_2$ are color-compatible paths and every vertex of $P_1$ is adjacent to every vertex of $P_2$. Thus, we may apply Lemma 3 to $P_1$ and $P_2$ and obtain a $\chi (D)$-rainbow path of D, a contradiction.

Thus, we may assume that every k-rainbow path $P_1$ of $D[X\cup \{v\}]$ contains v. Let $\mathcal {S}'$ be $\mathcal {S}$ restricted to $Y\cup \{v\}$. Suppose that $\mathcal {S}'$ is not a minimum coloring of $D[Y\cup \{v\}]$, i.e., $\chi (D[Y\cup \{v\}]) = \ell$. Note that this implies that v does not belong to a singleton color class of $\mathcal {S}$. Hence, $\mathcal {S}$ restricted to X must be a minimum k-coloring of D[X]. However there is a k-rainbow path in D[X] that does not contain v, a contradiction to our assumption. So we may assume that $\mathcal {S}'$ is a minimum coloring of $D[Y \cup \{v\} ]$ and hence $\chi (D[Y\cup \{v\}]) = \ell + 1$. Since, by our assumption, no vertex in Y belongs to the same color class of v in $\mathcal {S}$, it follows that v must belong to a singleton color class in $\mathcal {S}'$. Thus, there is an $(\ell + 1)$-rainbow path $P_3$ in $D[Y\cup \{v\}]$ that contains v. Hence, assume that $P_1 = (x_1, \ldots , x_i = v, x_{i+1}, \ldots , x_{k})$ and $P_3 = (y_1, \ldots , y_j=v, y_{j+1}, \ldots , y_{\ell + 1})$. Moreover, every vertex in $\{x_1, \ldots , x_{i-1}, x_{i+1}, \ldots , x_{k}\}$ is adjacent to every vertex in $\{y_1, \ldots , y_{j-1}, y_{j+1}, \ldots , y_{\ell +1}\}$. By Lemma 3 there is a path $R_1$ such that $V(R_1) = \{x_1, \ldots , x_{i-1}, y_1, \ldots , y_{j-1}\}$ and $ter(R_1) \in \{x_{i-1}, y_{j-1}\}$. Similarly, there is a path $R_2$ such that $V(R_2)=\{x_{i+1}, \ldots , x_k, y_{j+1}, \ldots , y_{\ell + 1}\}$ and $ini(R_2) \in \{x_{i+1}, y_{j+1}\}$. Since v is dominated by both $x_{i-1}$ and $y_{j-1}$ and v dominates both $x_{i+1}$ and $y_{j+1}$, it follows that $R_1vR_2$ is a $\chi (D)$-rainbow path of D, a contradiction.    $\blacksquare$

We may now restrict our attention to color-critical graphs whose complement is connected. We present below some results that provide us information on the number of vertices and on the properties of minimum colorings in such graphs (and so, in minimal non-$\chi$-diperfect digraphs).

In 1963, Gallai [4] showed a lower bound on the number of vertices of a graph that is color-critical and whose complement is connected. In 2002, Stehlík [13] proved a slightly stronger result that implies Gallai’s lower bound.

Theorem 9

(Gallai [4]). Let G be a color-critical graph. If $\overline{G}$ is connected, then G has at least $2\chi (G) - 1$ vertices.

Theorem 10

(Stehlík [13]). Let G be a color-critical graph and let $v \in V(G)$. If $\overline{G}$ is connected, then $G - v$ has a $(\chi (G) - 1)$-coloring in which every color class has at least two vertices.

The following results are specific for digraphs with stability number two.

Lemma 5

Let G be the underlying graph of an obstruction. If G has stability number two, then G has exactly $2\chi (G) - 1$ vertices.

Proof

By Lemmas 2 and 4, G is a color-critical and $\overline{G}$ is connected. Let $n = |V(G)|$. By Theorem 9, it follows that $n \ge 2\chi (G) - 1$. Towards a contradiction, suppose that $n > 2\chi (G) - 1$. Let $v \in V(G)$ and let $G' = G - v$. Note that $G'$ has at least $2\chi (G) - 1$ vertices and $\alpha (G') \le 2$. Thus, $\chi (G') \ge \Bigl \lceil \frac{2\chi (G)-1}{2} \Bigr \rceil \ge \chi (G)$. However, this is a contradiction since G is color-critical and, hence, $\chi (G') = \chi (G) - 1$.    $\blacksquare$

Corollary 1

Let G be the underlying graph of an obstruction. If G has stability number two, then in every minimal coloring of G there exists exactly one singleton color class and every other color class has size two.    $\blacksquare$

We use the concepts of (perfect) matching as defined in [2]. A graph F is factor-critical if $F - v$ has a perfect matching, for any $v \in V(F)$.

Corollary 2

Let G be the underlying graph of an obstruction. If G has stability number two, then $\overline{G}$ is factor-critical. Moreover, every minimum coloring of G corresponds to a maximum matching of $\overline{G}$ and vice versa.

Proof

Let $u \in V(G)$ and let $\mathcal {S}$ be a minimum coloring in which u is a singleton color class (such coloring exists by Theorem 8). By Corollary 1, it follows that $\{u\}$ must be the only singleton color class of $\mathcal {S}$ and every other color class of $\mathcal {S}$ has size two. Let $F = \overline{G}$. We may build a perfect matching M of $F - u$ by converting each color class $\{v_1, v_2\}$ of $\mathcal {S}\setminus \{u\}$ into an edge $v_1v_2$ of M.    $\blacksquare$

4 New Obstructions

We were able to find a few more examples of obstructions that were not yet known. All these digraphs have stability number two or three and they can be found in de Paula Silva’s master’s dissertation [8]. At this moment, we do not know if there are obstructions with stability number greater than three distinct from the conflicting odd cycles.

In this paper, we particularly focus on obstructions with stability number two. Two examples of such digraphs are depicted in Fig. 1. One may verify by inspection that neither of these digraphs contain conflicting odd cycles or non-$\chi$-diperfect super-orientations of $\overline{C_{2k+1}}$, with $k\ge 2$. Note that the underlying graph of both digraphs are spanning 4-chromatic subgraphs of a $\overline{C_7}$. We observe that the underlying graph of all the obstructions with stability number two that we have found are spanning $(k+1)$-chromatic subgraphs of a $\overline{C_{2k+1}}$ with $k\ge 3$. In fact, we may show that we can build an obstruction from some non-$\chi$-diperfect super-orientation of a $\overline{C_{2k+1}}$ with $k\ge 3$, as we state in Lemma 6. Due to space limitation, we are not able to present the proof of this result here, but it can also be found in [8].

Lemma 6

(de Paula Silva, Nunes da Silva and Lee [8]). For every $k \ge 3$, there is an obstruction that is obtained by deleting an arc from some non-$\chi$-diperfect super-orientation of a $\overline{C_{2k+1}}$.    $\blacksquare$

Fig. 1.

Obstructions with stability number two.

In view of such observations, we decided to investigate digraphs with stability number two whose underlying graph does not contain a spanning $(k+1)$-chromatic subgraph of a $\overline{C_{2k+1}}$ with $k\ge 3$. In fact, we were able to characterize which of these digraphs are $\chi$-diperfect and we present our result in next section.

5 Characterization of a Special Class

Recall that $\mathcal {H}$ is the family of digraphs such that $D \in \mathcal {H}$ if and only if $\alpha (D)=2$ and for every induced subdigraph $D'$ of D it follows that U(D) is not a spanning $(k+1)$-chromatic subgraph of $\overline{C_{2k+1}}$ with $k \ge 3$. Note that this is equivalent to saying that every (not necessarily induced) odd cycle of $\overline{U(D)}$ has length five.

Let G be the underlying graph of an obstruction. By Lemma 4, $\overline{G}$ is 2-connected. Moreover, Corollary 2 states that if $\alpha (G)=2$, then $\overline{G}$ is factor-critical and every maximum matching of $\overline{G}$ corresponds to a minimum coloring of G and vice versa. We present now some auxiliary results on 2-connected factor-critical graphs that are helpful in understanding the structure of these digraphs.

Lemma 7

Let F be a factor-critical graph and let $u^* \in V(F)$. Let M be a perfect matching of $F - u^*$. Then, there is an odd cycle C in F such that $u^* \in V(C)$ and M restricted to $F - V(C)$ is a perfect matching.

Proof

Let v be a vertex that is adjacent to $u^*$. Let $M'$ be a perfect matching of $F - v$. Then, in $M \varDelta M'$ there is an even path P from $u^*$ to v whose edges alternate between M and $M'$. So, $C = P + u^*v$ is an odd cycle. Since the only vertex not covered by M restricted to C is $u^*$, M restricted to $M - C$ is a perfect matching.    $\blacksquare$

Let G be a graph and let $G'$ be a subgraph of G. A path $P=(v_1,v_2\ldots ,v_\ell )$ is an ear of $G'$ if $v_1, v_\ell \in V(G)$ and $v_2,\ldots ,v_{\ell -1} \in V(G) \setminus V(G')$. In other words, the extremes of P belong to $G'$ but the internal vertices do not. An ear decomposition of G is a sequence $(G_1,G_2,\ldots ,G_\ell )$ of subgraphs of G such that

• $G_1$ is a cycle,

• $G_{i+1} = G_i \cup P_i$, where $P_i$ is an ear of $G_i$ with $1 \le i < \ell$, and

• $G_\ell = G$.

If every ear in $\{P_1, \ldots , P_{\ell - 1}\}$ has odd length, then we say that $(G_1,G_2,\ldots ,G_\ell )$ is an odd-ear decomposition of G. In 1972, Lovász [7] proved the following characterization of 2-connected factor-critical graphs.

Theorem 11

(Lovász [7]). A 2-connected graph F is factor-critical if and only if F has an odd-ear decomposition starting with an odd cycle.

Let F be a graph with $2k+1$ vertices, for $k\ge 2$ and with at least one induced cycle C of length five. We say that F is nice if the vertices of C can be labelled as $u_1,\ldots ,u_5$ and the vertices of $F - V(C)$ can be labelled as $x_1,\ldots ,x_{k-2},y_1,\ldots ,y_{k-2}$ so that

• for $i \in \{1,\ldots ,k-2\}$, the neighbors of $x_i$ are $y_i$ and $u_1$, and

• for $i \in \{1,\ldots ,k-2\}$, the neighbors of $y_i$ are $x_i$ and $u_3$.

Thus, for every $i \in \{1,\ldots ,k-2\}$, it follows that $(u_1, x_i, y_i, u_3, u_2, u_1)$ is an induced $C_5$ (see Fig. 2 for an example with $k=4$).

We may characterize nice graphs in terms of odd-ear decompositions. We state such characterization below for ease of further reference.

Proposition 1

A graph F is nice if and only if there is an odd-ear decomposition $(F_1, F_2,\ldots ,F_\ell )$ of F such that:

• (a) $F_1$ is an odd cycle of length five,

• (b) $F_{i+1} = F_i \cup P_i$, where $P_i$ is an ear of length three of $F_1$ with $1\le i < \ell$, and

• (c) all the ears $P_1, \ldots ,P_{\ell - 1}$ have as extremes the same pair of non-adjacent vertices of $F_1$.    $\blacksquare$

Fig. 2.

Nice graph with nine vertices.

We can easily check that every odd cycle of a nice graph must have length five. Moreover, by Theorem 11, a nice graph is 2-connected and factor-critical. In fact, we prove that every 2-connected factor-critical graph in which every odd cycle has length five must be isomorphic to a nice graph. Before we present such result, we need an auxiliary lemma.

Lemma 8

Let F be a graph in which every odd cycle has length five and let C be an odd cycle of F. Let P be an ear of C. If the extremes of P are non-adjacent in C, then the length of P is two or three. Otherwise, the length of P is four.

Proof

Let $C=(u_1,\ldots ,u_5)$ be an odd cycle of F and let $P=(v_1, \ldots ,v_\ell )$ be an ear of C. Suppose first that the extremes of P are non-adjacent, say $v_1=u_1$ and $v_\ell = u_3$. Since F has no cycle of length three, the length of P is at least two. Towards a contradiction, assume that the length of P is greater than three (so $\ell \ge 5$). Then, either $(v_1=u_1,v_2,\ldots ,v_\ell =u_3,u_2,u_1)$ or $(v_1=u_1,v_2,\ldots ,v_\ell =u_3,u_4,u_5,u_1)$ is an odd cycle of length greater than five, a contradiction. So suppose that the extremes of P are adjacent, say $v_1=u_1$ and $v_\ell =u_2$. Towards a contradiction, suppose that the length of P is distinct from four (so $\ell \ne 5$). Then either $(v_1=u_1,v_2,\ldots ,v_\ell =u_2,u_1)$ or $(v_1=u_1,v_2,\ldots ,v_\ell =u_2,u_3,u_4,u_5,u_1)$ is an odd cycle of length distinct from five, a contradiction.    $\blacksquare$

Lemma 9

Let F be a 2-connected factor-critical graph. If every odd cycle of F has length five, then F is isomorphic to a nice graph.

Proof

By Theorem 11, F has an odd-ear decomposition $(F_1, \ldots , F_\ell )$ in which $F_1$ is an odd cycle. Let $\{P_1,\ldots ,P_{\ell -1}\}$ be the ears in such ear-decomposition. We show by induction on $\ell$ that conditions (a) to (c) from Proposition 1 hold for $(F_1, \ldots , F_\ell )$. Since every odd cycle of F has length five, condition (a) immediately holds. Let $C = F_1 = (u_1, u_2, u_3, u_4, u_5, u_1)$. Clearly, if $\ell =1$ then $F = C$ is a nice graph. Suppose now that $\ell =2$. Since $P_1$ is an ear of C (of odd length), by Lemma 8, its length is exactly three and its extremes are non-adjacent vertices of C. So property (b) is satisfied and property (c) trivially holds. So we may assume that $\ell \ge 3$. By Theorem 11, $F_{\ell -1}$ is a 2-connected factor-critical graph and, clearly, every odd cycle of $F_{\ell -1}$ must have length five. Thus, by induction hypothesis, $F_{\ell - 1}$ is a nice graph. By properties (b) and (c) from Proposition 1, we may assume that $P_i = (u_1,x_i,y_i,u_3)$ for every $i\in \{1,\ldots ,\ell -2\}$. Now, it suffices to show that $P_{\ell -1}$ is an ear of C whose extremes are $u_1$ and $u_3$.

First, we show that $P_{\ell -1}=(z_1,\ldots ,z_t)$ is an ear of C. Towards a contradiction, suppose that at least one extreme of $P_{\ell -1}$ does not belong to C. We may assume without loss of generality that $z_1 = x_1$. Suppose first that $z_t \notin V(C)$. If there is j such that $z_t = y_j$ then $(u_1, z_1=x_1,\ldots ,z_t=y_j,u_3)$ is an ear that contradicts Lemma 8 (see Fig. 3a for the case where $j=1$ and see Fig. 3b for the case where $j > 1$). So we may assume that there is j such that $z_t = x_j$. Then $(u_3,y_1,x_1=z_1,\ldots ,z_t=x_j,u_1)$ is an ear of C that contradicts Lemma 8 (see Fig. 3c). Hence, we may assume that $z_t \in V(C)$.

Fig. 3.

Auxiliary illustration for the proof of Lemma 9.

Since F has no $C_3$, it follows that $z_1=x_1$ is non-adjacent to vertices $u_2, u_3$ and $u_5$. So, if the length of $P_{\ell -1}$ is one, then $P_{\ell -1}=(x_1,u_4)$ and $(u_3, y_1, x_1, u_4)$ is an ear of C that contradicts Lemma 8 (see Fig. 3d). Thus, we may assume that the length of $P_{\ell -1}$ is at least three (so $t \ge 4$). If $z_t = u_3$, then $(u_1, z_1=x_1,\ldots ,z_t=u_3)$ is an ear of C that contradicts Lemma 8 (see Fig. 3e). Otherwise, $(u_3,y_1,x_1=z_1,\ldots ,z_t)$ is an ear of C of length greater than four, a contradiction to Lemma 8 (see Fig. 3f for an example with $z_t = u_5$). Since all cases lead us to a contradiction, it follows that $P_{\ell -1}$ must be an ear of C. Also, recall that $P_{\ell -1}$ has odd length by definition. By Lemma 8, it must have length three, i.e., $P_{\ell -1}=(z_1,z_2,z_3,z_4)$ and, furthermore, $z_1$ and $z_4$ are non-adjacent. Thus, property (b) is satisfied.

Now we show that property (c) of Proposition 1 holds for $P_{\ell -1}$, i.e., we show that $z_1=u_1$ and $z_t=u_3$. Towards a contradiction, suppose that $z_1=u_2$ and $z_4=u_4$. Then, $(u_1, x_1, y_1, u_3, z_1=u_2, z_2, z_3, z_4=u_4, u_5, u_1)$ is a $C_9$, a contradiction (see Fig. 3g). The argument is analogous to show that the extremes of $P_{\ell -1}$ cannot be $u_2$ and $u_5$. So suppose that $z_1=u_1$ and $z_4=u_4$. Then, $(z_1=u_1, x_1, y_1, u_3, u_4=z_4, z_3, z_2, z_1=u_1)$ is a $C_7$, a contradiction (see Fig. 3h). The argument is analogous to show that the extremes of $P_{\ell -1}$ cannot be $u_3$ and $u_5$. Hence, the extremes of $P_{\ell -1}$ must be $u_1$ and $u_3$.    $\blacksquare$

The next proposition is an immediate consequence of Lemma 7 and it can be easily verified recalling that, by Corollary 2, the complement of a color-critical graph G with $\alpha (G)=2$ is factor-critical and every maximum matching of $\overline{G}$ corresponds to a minimum coloring of G.

Proposition 2

Let G be the complement of a nice graph and let $\mathcal {S}$ be a minimum coloring of G. Then, there is an induced cycle $C = C_5$ of G such that the vertices of C can be labelled as $(v_1, \ldots , v_5, v_1)$ and the vertices in $V(G) - V(C)$ can be labelled as $x_1, \ldots , x_{k-2}, y_1, \ldots , y_{k-2}$ so that:

(a):

the vertex $u^*$ in the singleton color class of $\mathcal {S}$ belongs to V(C),

(b):

$\{x_i, y_i\}$ is a color class of $\mathcal {S}$ for $i \in \{1, \ldots , k-2\}$,

(c):

for $i \in \{1, \ldots , k-2\}$, the non-neighbors of $x_i$ are $y_i$ and $v_1$,

(d):

for $i \in \{1, \ldots , k-2\}$, the non-neighbors of $y_i$ are $x_i$ and $v_2$, and

(e):

$(v_1, y_i, v_4, x_i, v_2, v_1)$ is an induced odd cycle of length five.

   $\blacksquare$

Henceforth, we may assume that every complement of a nice graph has a fixed minimum coloring $\mathcal {S}$ and its vertices are labelled as described in Proposition 2. Note that the cycle $(v_1, \ldots , v_5, v_1)$ of G is the complement of the cycle $(u_1, \ldots , u_5, u_1)$ mentioned on the definition of a nice graph and on Lemma 9 (see Fig. 4). We use the notation $X \mapsto Y$ to denote that every vertex of X dominates every vertex of Y in D and no vertex of Y dominates a vertex of X in D. If $X=\{u\}$ (respectively, $Y=\{v\}$), we may write directly $u \mapsto Y$ (respectively, $X \mapsto v$).

Fig. 4.

Example of labelling of a complement of a nice graph with nine vertices.

Lemma 10

Let D be a super-orientation of the complement of a nice graph with $2k + 1$ vertices, for $k \ge 2$. If D contains no conflicting odd cycle as an induced subdigraph, then D has a $(k+1)$-rainbow path.

Proof

By hypothesis, D contains no conflicting odd cycle. Then, by Theorem 4, C has a 3-rainbow path P. Let $X = \{x_1,\ldots ,x_{k-2}\}$ and let $Y=\{y_1,\ldots ,y_{k-2}\}$. Note that D[X] and D[Y] induce semicomplete digraphs and they are both color-compatible with P. Suppose first that $v_1 \notin V(P)$. In this case, every vertex in X is adjacent to every vertex of P. By Theorem 1, D[X] has a hamiltonian path $P'$. We may apply Lemma 3 to $P'$ and P, and obtain a $(k+1)$-rainbow of D. The argument is symmetric in the case where $v_2 \notin V(P)$. Hence, we may assume that every 3-rainbow path P of C contains both $v_1$ and $v_2$. Note that, since $v_4$ is non-adjacent to both $v_1$ and $v_2$, we know that $v_4 \ne u^*$. Also, we may assume without loss of generality, that $u^* = v_1$ or $u^* = v_5$. In both cases, note that $v_1$ and $v_4$ belong to distinct color classes. We consider the following two cases.

Case 1

There is no digon between $v_1$ and $v_2$.

By the Principle of Directional Duality, we may assume that $v_1 \mapsto v_2$. Let $i \in \{1,\ldots ,k-2\}$. Suppose that $v_1 \mapsto y_i$ and $x_i \mapsto v_2$. Since $C' = (v_4, y_i, v_1, v_2, x_i, v_4)$ is an induced $C_5$ by definition, it follows that $v_4$ must be dominated by $y_i$. Otherwise, $(v_1, y_i)$ and $(v_1, v_2)$ would be two arc-disjoint odd sectors of $C'$. Hence, $C'$ is a conflicting odd cycle, a contradiction (see Fig. 5a). Thus, $P'=(v_1, y_i, v_4)$ is a 3-rainbow path of $C'$. Let $Z = (Y \setminus \{y_i\}) \cup \{v_5\}$. Similarly to what happened before, D[Z] induces a semicomplete digraph that is color-compatible with $P'$. Moreover, every vertex of Z is adjacent to every vertex of $P'$. Since, by Theorem 1, there is a hamiltonian path R in D[Z], we may obtain a $(k+1)$-rainbow path of D by applying Lemma 3 to $P'$ and R.

Hence, we may assume that, there is no $i \in \{1,\ldots ,k-2\}$ such that $v_1 \mapsto y_i$ and $x_i \mapsto v_2$. Let $Y^-$ be the subset of vertices of Y that dominate $v_1$ and let $X^+$ be the subset of vertices of X such that $x_i \in X$ if and only if $y_i \notin Y$. Note that, by our assumption, $v_2$ must dominate every vertex in $X^+$.

Fig. 5.

Auxiliary illustration for the proof of Lemma 10

Recall that every 3-rainbow path P of C contains both $v_1$ and $v_2$ and $v_1 \mapsto v_2$. Hence, $P=(v_5, v_1, v_2)$ or $P=(v_1, v_2, v_3)$. Thus, $\{v_1, v_2, v_5\} \cup Y^- \cup X^+$ or $\{v_1, v_2, v_3\} \cup Y^- \cup X^+$ contains exactly one vertex of each color class of $\mathcal {S}$. If $P=(v_5, v_1, v_2)$, let $T^- = Y^- \cup \{v_5\}$ and let $T^+ = X^+$; otherwise let $T^- = Y^-$ and let $T^+ = X^+ \cup \{v_3\}$. By Theorem 1, $D[T^-]$ has a hamiltonian path $P_1$ and $D[T^+]$ has a hamiltonian path $P_2$. Since every vertex of $T^-$ dominates $v_1$ and $v_2$ dominates every vertex of $T^+$, it follows that $P_1v_1v_2P_2$ is a $(k+1)$-rainbow path of D (see Fig. 5b).

Case 2

There is a digon between $v_1$ and $v_2$.

By the Principle of Directional Duality, we may assume that $v_5$ dominates $v_1$. Let $Y^-$ be the subset of vertices of Y that dominate $v_1$. Let $X^-$ be the subset of vertices of X such that $x_i \in X^-$ if and only if $y_i \notin Y^-$ and $x_i$ dominates $v_2$. Let $W = X^- \cup Y^- \cup \{v_5\}$.

So, if there is a color class $\{x_i, y_i\}$ such that $x_i \notin W$ and $y_i \notin W$, then $v_1$ dominates $y_i$ and $v_2$ dominates $x_i$. Let $X^+$ be the subset of vertices of X such that $x_i \notin W$ and $y_i \notin W$ and let $Y^+$ be the subset of vertices of Y such that $x_i \notin W$ and $y_i \notin W$. Note that $x_i \in X^+$ if and only if $y_i \in Y^+$ and, hence, $|X^+| = |Y^+|$. Moreover, note that $D[W \cup \{v_1,v_2\}]$ is color-compatible with $D[X^+]$ and $D[Y^+]$, and $D[W], D[X^+], D[Y^+]$ induce semicomplete digraphs (see Fig. 5c). Let $P', P_1$ and $P_2$ be hamiltonian paths of $D[W], D[X^+], D[Y^+]$, respectively (such paths exist by Theorem 1). If $ter(P')$ dominates $v_1$, then $P'v_1v_2P_2$ is a $(k+1)$-rainbow path of D. Otherwise, $ter(P')$ dominates $v_2$ and $P'v_2v_1P_1$ is a $(k+1)$-rainbow path of D.    $\blacksquare$

Theorem 12

Let D be a digraph in which every odd cycle of $\overline{U(D)}$ has length five. Then, D is $\chi$-diperfect if and only if D does not contain a conflicting odd cycle as an induced subdigraph.

Proof

(Necessity) The necessity immediately follows by Theorem 4.

(Sufficiency) To show that D is $\chi$-diperfect, it suffices to prove that, for any minimum coloring of D, there is a $\chi (D)$-rainbow path in D. So towards a contradiction, suppose that D is an obstruction i.e. there is a minimum coloring of D that does not admit a $\chi (D)$-rainbow path but every proper induced subdigraph is $\chi$-diperfect. Let $G = U(D)$. By Lemmas 2 and 4, we may assume that G is color-critical and that $\overline{G}$ is 2-connected. Since, by hypotheses, every odd cycle of $\overline{G}$ has length five, it follows that $\alpha (G)=2$. By Corollary 2, $\overline{G}$ is a factor-critical graph. Hence, by Lemma 9, $\overline{G}$ is isomorphic to a nice graph. Thus, by Lemma 10, D has a $\chi (D)$-rainbow path, a contradiction.    $\blacksquare$

6 Final Remarks

In this paper we showed that there are minimal non-$\chi$-diperfect digraphs whose underlying graphs are neither an odd cycle of length at least five nor its complement; all these obstructions we have found have stability number two or three. In particular, the underlying graph of an obstruction with stability number two that we have found is a subgraph of some complement of an odd cycle of length at least seven.

Motivated by this fact we investigated a class of digraphs whose underlying graphs have stability number two such that every odd cycle of their complement has length exactly five. We proved that a digraph in this class is $\chi$-diperfect if and only if it does not contain an induced conflicting odd cycle. The proof we presented is not straightforward, which suggests that figuring out the set of obstructions may be difficult. It is still open whether there is some obstruction with stability number at least four that is not a conflicting odd cycle.