The degree d(v) of a vertex v in a graph G is the number of edges in G containing v. The length of a path or a cycle is the number of edges in it. A graph is even-hole-free if it does not contain an induced cycle of even length. Even-hole-free graphs are the subject of intense interest and study in structural graph theory. Much is known about the structure of even-hole-free graphs: for example, even-hole-free graphs have a decomposition theorem [4], are known to have bisimplicial vertices (vertices whose neighborhoods are the union of two cliques) [2], and can be recognized in polynomial time [3]. Even-hole-free graphs have also been well-studied with respect to algorithmic parameters such as independence number, chromatic number, and treewidth. See [6] for a survey of even-hole-free graphs.
A graph is chordal if it contains no induced cycles of length four or greater. In 2020, Sivaraman conjectured that every even-hole-free graph can be written as the union of two chordal induced subgraphs [5]. In this paper, we prove Sivaraman's conjecture under an additional assumption.
A wheel (H, w) is a hole H and a vertex w ∈ V (G) \ H such that |N (w) ∩ H| ≥ 3. A universal wheel is a wheel (H, w) such that w is complete to H. A sector wheel is a wheel (H, w) such that either (H, w) is a universal wheel or N (w) ∩ H is a path. A pair (X 1 , X 2 ) of vertex subsets of G such that X 1 ∪ X 2 = V (G) and G[X 1 ] and G[X 2 ] are chordal is called a chordal cover of G. We prove: Theorem 1.1. Every even-hole-free graph with no sector wheel admits a chordal cover.
Our proof depends on a decomposition theorem for even-hole-free graphs proved in [4]. We first need some definitions. Let T be a tree and write V 1 , V 2 for its two sides when viewed as a bipartite graph. Let L denote the set of leaves of T and write
For each v ∈ L we write e(v) for the unique edge of T incident with v. We construct a graph B(T ) as follows: the set of vertices of B(T ) is E(T ) ∪ {x 1 , x 2 }, where x 1 , x 2 are two additional vertices. Two vertices of B(T ) are adjacent if one of the following holds:
• They represent two edges of T with a common vertex, or
• one of them is x i and the other is e(v) and v ∈ L i for some i ∈ {1, 2}, or
• they are x 1 and x 2 .
Note that the vertex set of every induced cycle in B(T ) with at least 4 vertices consists of the edge set of some path in T between two leaves together with either x 1 or x 2 or both. A graph G is an extended nontrivial basic graph if G = B(T ) for some tree T with at least three leaves and at least two non-leaves. (Note that if T is a path graph then B(T ) is a cycle, and if T is a star then B(T ) is a clique. Hence it makes sense to exclude these cases and deal with them separately.)
A 2-join of a graph G is a partition
such that the following hold:
, and there are no other edges of E(G) with one end in
and
where k may be 0), which we call the marker path for Z i , and Z i is not just this path.
A pyramid is a graph consisting of a vertex a called the apex, a triangle b 1 b 2 b 3 called the base, and three paths P i from a to b i , each of which has length at least one, at most one of which has length exactly one, such that the only edge from
We now can state the decomposition theorem we use: 4]). Let G be an even-hole-free graph. Then one of the following holds:
• G is a clique;
• G is a hole;
• G is a pyramid;
• G is an extended nontrivial basic graph;
• G has a 2-join; or
• G has a star cutset.
Let G be an even-hole-free graph with no sector wheel. The main idea of our proof is to start with a "precover" of G, i.e. two sets W 1 , W 2 ⊆ V (G) such that G[W 1 ] and G[W 2 ] are chordal, and extend the precover to a chordal cover of G by finding sets and G[X 1 ] and G[X 2 ] are chordal. We define the "precover" using flat paths in G.
For a path P = (v 1 , . . . , v k ), we write N [P ] for the set of vertices either in the path or with at least one neighbor in the path. We define the interior of P to be int(P ) = {v 2 , . . . , v k-1 }. For k ∈ {1, 2} we set int(P ) = ∅. We say that an induced path P is flat if all the vertices in its interior have degree 2 in G. Note that every path with either 1 or 2 vertices is flat.
We say that a graph G is flat path extendable (FPE) if for every induced flat path P and every two sets
If G is not FPE but every proper induced subgraph of G is FPE, then we say that G is minimal non flat path extendable (MNFPE), and for a path P not satisfying the above property (i.e., there exist two sets
are chordal and X 1 ∩ X 2 = V (P ) and X 1 ∪ X 2 = V ) we say that P is a witness path for G and that W 1 , W 2 are the corresponding witness sets.
We prove the following theorem:
Theorem 1.3. Every graph with no even hole, no sector wheel, and no star cutset is FPE.
To deal with the case when G contains a star cutset, we define a closely related concept called weakly flat path extendable. A graph G is weakly flat path extendable (weakly FPE) if for every path P of length zero or one, and every two sets
. Under these conditions, (P, W 1 , W 2 ) is a precover and (X 1 , X 2 ) is a chordal cover of G that extends (P, W 1 , W 2 ). (The only difference between weakly flat path extendable and flat path extendable is that weakly flat path extendable only considers paths of length at most one). We note the following relationships between FPE and weakly FPE:
We prove: Theorem 1.4. Every graph with no even hole and no sector wheel is weakly FPE. Proof of Theorem 1.1. Let G be an even-hole-free graph with no sector wheel. Let v ∈ V (G). Since G has no sector wheel, it follows that
) is a precover of G. By Theorem 1.4, G is weakly FPE, so G admits a chordal cover. This completes the proof.
Theorem 1.4 is not true without the assumption that the graph has no sector wheel. Indeed, consider the graph G depicted in Figure 1.1. Let P = {x} and let
Therefore the method in this paper cannot be extended to the case of graphs containing sector wheels without some new ideas.
In Section 2, we prove that if G is an extended nontrivial basic graph, then G is FPE. In Section 3, we prove that if G has no clique cutset and no star cutset, then G is FPE. In Section 4, we prove that if G admits a clique cutset, then G is weakly FPE. In Section 5, we prove that if G admits a proper star cutset, then G is weakly FPE. Finally, in Section 6, we prove Theorem 1.4.
In this section, we prove that extended nontrivial basic graphs with no star cutsets are FPE. A vertex v in a graph G is nearly simplicial if N (v) is the union of a clique and a singleton. First we show that every nearly simplicial vertex in an MNFPE graph G is contained in the neighborhood of every witness path for G. Proof. Let W 1 and W 2 be the witness sets for P . Suppose there exists a nearly simplicial vertex
Lemma 2.2. Let G = B(T ) be an extended nontrivial basic graph for some tree T . If there are two leaves of T with a common neighbor, then B(T ) has a star cutset.
Proof. Let t 1 and t 2 be two leaves of T with a common neighbor u, and let ℓ 1 and ℓ 2 be the vertices of B(T ) corresponding to the edges {u, t 1 } and {u, t 2 }, respectively. Up to symmetry between x 1 and x 2 , assume that x 1 is adjacent to ℓ 1 . Since t 1 and t 2 have distance 2, which is an even number, it follows that x 1 is adjacent to ℓ 2 , and that {ℓ 1 , ℓ 2 } is anticomplete to x 2 . Then, the neighborhood of ℓ i for i = 1, 2 consists of x 1 and the vertices of B(T ) corresponding to exactly the edges incident with the common neighbor of t 1 and t 2 . In particular, N B(T
Since we deal with graphs with clique cutsets and proper star cutset separately in Sections 4 and 5, respectively, we may assume here that there are no two leaves in T with a common neighbor.
Lemma 2.3. Let T be a tree, let G = B(T ) be an extended nontrivial basic graph, and assume that B(T ) has no star cutset. Then B(T ) is not MNFPE.
Proof. We assume for contradiction that there exists a witness path P for B(T ). If T is a path then B(T ) is a cycle and therefore is clearly FPE. It follows that at least one of x i has degree at least 3, so not both x 1 , x 2 are internal in P .
Let (t 1 , t 2 , . . . , t k ) be the longest path in T . Assuming T is not a path and there are no two leaves of T with a common neighbor, we must have k ≥ 5 and d(t 2 ) = d(t k-1 ) = 2. Note that if x i is internal in P then x 3-i is in P . Indeed, suppose x 1 is internal in P . Then, by definition of a witness path, x 1 has degree 2, and its two neighbors are also in P , implying x 2 ∈ P .
Suppose k = 5. Then T is a subdivision of a star, with t 3 being its center. In this case, all the edges of T are nearly simplicial in B(T ), and therefore, by Lemma 2.1, all of them are in N [P ], as vertices in B(T ). Moreover, P must contain at least one of the vertices x 1 and x 2 , for otherwise, there is some nearly simplicial vertex not in N [P ], contradicting Lemma 2.1. Thus N [P ] = V (B(T )). This is impossible, since we have W 1 ∪ W 2 = N [P ]. So from now on we assume k > 5.
Since no two leaves of T have a common neighbor, by Lemma 2.1, we have that {t 1 , t 2 }, {t 2 , t 3 }, {t k-2 , t k-1 }, and {t k-1 , t k } are all in N [P ] since they are nearly simplicial. Since {t 2 , t 3 } ∈ N [P ], some edge of T that is incident with either t 2 or t 3 must be in V (P ). Similarly, since {t k-2 , t k-1 } ∈ N [P ], some edge of T that is incident with either t k-2 or t k-1 must be in V (P ). Since not both x 1 , x 2 are internal in P , this implies, by induction, that {t 3 , t 4 }, . . . ,
we must have {t 2 , t 3 } ∈ V (P ) and similarly, since
We conclude that T is a path, which yields a contradiction as discussed above.
In this section, we prove that every (even hole, sector wheel)-free graph with no star cutset is FPE. We first focus on the case when G admits a 2-join. If G admits a 2-join (A 1 , C 1 , B 1 , A 2 , C 2 , B 2 ), we denote by B(Z i ) the graph formed by adding to Z i = A i ∪ C i ∪ B i the marker path M 3-i . We call B(Z 1 ) and B(Z 2 ) the blocks of decomposition of the 2-join (A 1 , C 1 , B 1 , A 2 , C 2 , B 2 ). We need the following theorem from [4]: Theorem 3.1 ([4], Theorem 2.10). If G is even-hole-free and has no star cutset, then B(Z 1 ) and B(Z 2 ) have no star cutset.
The next lemma states how paths and holes interact with the structure of a 2-join. Lemma 3.2. Let G be a graph and let
) is an induced C 4 , contradicting the fact that G has no even holes, or Q ∩ (A 1 ∪ A 2 ) contains K 4 minus an edge as a subgraph, contradicting the fact that Q is a path or a hole. Therefore, up to symmetry we may assume that 3 as a subgraph, contradicting the fact that Q is a path or a hole. Lemma 3.2 has the following useful corollary.
and note that a 2 ∈ P . Since a 2 has two neighbors in P , namely P ∩ A 1 , it follows that a 2 is an interior vertex of P , so by the definition of flat path, a 2 has degree two in G. But by the definition of 2-join, there is a path with ends in A 2 and B 2 and interior in C 2 , so a 2 has a neighbor in B 2 ∪ C 2 , a contradiction. This completes the proof.
Next, we prove that if a graph G admits a 2-join, then chordal covers of the blocks of decompositions of the 2-join can be combined into a chordal cover of G. Lemma 3.4. Let G be a graph with no even hole. Assume that G admits a 2-join
2 ) be chordal covers of G 1 and G 2 , respectively. Further assume that:
where a 1 and b 1 are the ends of M 1 in A 1 and B 1 , respectively.
Let
Therefore, H contains an edge with one end in Z 1 and one end in Z 2 . By Lemma 3.2, one of the following holds:
(1) H ∩ Z 1 is independent and consists of at most one vertex of A 1 and at most one vertex of B 1 , or (2) H ∩ Z 2 is independent and consists of at most one vertex of A 2 and at most one vertex of B 2 , or (3) H ∩ Z 1 is a path with ends in A 1 and B 1 and (possibly empty) interior in C 1 and H ∩ Z 2 is a path with ends in A 2 and B 2 and (possibly empty) interior in C 2 .
First, suppose (1) holds. We claim that if
is a twin wheel of G, contradicting that G has no sector wheel. This proves that |A 1 | = 1, and so
1 , and by the second assumption of the lemma, H ∩Z 1 ⊆ X ′′ 1 . It follows that H ⊆ X ′′ 1 , contradicting the chordality of X ′′ 1 . Therefore, (1) does not hold.
Next, suppose (2) holds. Let H ′ be the hole of G 1 formed by replacing the vertex of H ∩ A 2 , if it exists, with a 2 , and replacing the vertex of
1 , and by the first assumption of the lemma, H ⊆ X ′ 1 . Now, H is a hole of X ′ 1 , contradicting the chordality of X ′ 1 . Therefore, (2) does not hold. Since (1) and (2) do not hold, it follows that (3) holds. Let
, by the first assumption of the lemma,
1 . This completes the proof.
By symmetry, the following lemma is also true: Lemma 3.5. Let G be a graph with no even hole. Assume that G admits a 2-join
) and G 2 = B(Z 2 ), and let (X ′ 1 , X ′ 2 ) and (X ′′ 1 , X ′′ 2 ) be chordal covers of G 1 and G 2 , respectively. Further assume that:
, where a 2 and b 2 are the ends of M 2 in A 2 and B 2 , respectively.
Let
Next, we prove that a partial precover can be extended to a full precover. Lemma 3.6. Let G be a graph with no even hole, no star cutset, and no sector wheel. Let
Proof. We construct W ′ 1 and W ′ 2 as follows. We begin by adding every vertex of W i to W ′ i for i = 1, 2. Then, as long as
. Note that since P is a flat path and by the assumptions of the lemma, v ∈ (N (p 1 ) ∪ N (p k )) \ (N (p 1 ) ∩ N (p k )).
First, suppose that P has length greater than one. Assume v ∈ N (p i ) \ N (p k+1-i ) for i ∈ {1, k}. We claim that v has at most one neighbor in N (p k+1-i ). Indeed, Suppose v has two neighbors x 1 , x 2 ∈ N (p k+1-i ). Since {p k+1-i , x 1 , x 2 , v} does not induce a C 4 , it follows that x 1 and x 2 are adjacent. If p i is adjacent to both x 1 and x 2 , then (P ∪ {x 1 }, x 2 ) is a twin wheel, contradicting that G has no sector wheel. Therefore, we may assume that p i is non-adjacent to x 1 . But now P ∪ {x 1 , v} is a hole and N (x 2 ) ∩ (P ∪ {x 1 , v}) is a path of length two, contradicting that G has no sector wheel.
We now follow the process below, which is well defined since v has at most one meighbor in N (p k+1-i ):
By the above, the sets W ′ 1 , W ′ 2 formed in this way are unique: every vertex v ∈ N (p i ) \ N (p k+1-i ) is assigned to exactly one of W ′ 1 , W ′ 2 as above. Now, suppose that P has length one. Assume v ∈ N (p i ) \ N (p k+i-1 ) for i ∈ {1, k}. We claim that v has at most one neighbor in N (p k+1-i ) \ N (p i ). Indeed, suppose v has two neighbors x 1 , x 2 ∈ N (p k+1-i )\N (p i ). Since {p k+1-i , x 1 , x 2 , v} does not induce a C 4 , it follows that x 1 and x 2 are adjacent. But now P ∪ {x 1 , v} is a hole and N (x 2 ) ∩ (P ∪ {x 1 , v}) is a path of length two, contradicting that G has no sector wheel.
We now follow the process below:
By (7), {v 0 , w 0 } ⊆ N (v) and by (6), {v 0 , w 0 } is not the center of a double star cutset of G, so for all 1 ≤ i ≤ j ≤ m, there exists a path Q = q 1 -. . . -q k from C i to C j that is anticomplete to {v 0 , w 0 } such that q 1 ∈ C i , q k ∈ C j , Q * ⊆ N (v). Let Q = q 1 -. . . -q k be the shortest such path. We may assume up to symmetry that i = 1 and j = 2. Let R ⊆ C 1 be the shortest path with one end q 1 such that R contains neighbors of both v 0 and w 0 . Similarly, let S ⊆ C 2 be the shortest path with one end q k such that S contains neighbors of both v 0 and w 0 . (Note that both R and S exist by (7)). Let R = q 1 -r 1 -. . . -r ℓ and let S = q k -s 1 -. . . -s t . Since R is the shortest path containing neighbors of both v 0 and w 0 , it follows that R \ {r ℓ contains neighbors of at most one of v 0 and w 0 . Similarly, S \ {s t } contains neighbors of at most one of v 0 and w 0 . We may assume that r ℓ is the unique neighbor of v 0 in R.
(8) w 0 has exactly one neighbor r w in R and r w ̸ = r ℓ .
Let H 1 be the hole given by H 1 = v 0 -v-q 2 -q 1 -R-r ℓ -v 0 . Since R contains neighbors of w 0 , it follows that w 0 has at least three neighbors in H 1 : v 0 , v, and a neighbor in R. By (5), w 0 is not the center of a star cutset of G. By Lemma 5.5, (H 1 , w 0 ) is a short pyramid. It follows that w 0 has exactly one neighbor r w in R and r w ̸ = r ℓ . This proves (8).
(9) Let {a, b} = {v 0 , w 0 } such that s t is the unique neighbor of a in S. Then, b has exactly one neighbor in S and b is non-adjacent to s t .
Let H 2 be the hole given by H 2 = a-v-q k-1 -q k -S-s t -a. Since S contains neighbors of b, it follows that b has at least three neighbors in H 1 : a, v, and a neighbor in S. By (5), b is not the center of a star cutset of G, and so by Lemma 5.5, (H 2 , w 0 ) is a short pyramid. It follows that b has exactly one neighbor s w in S and s w ̸ = s t . This proves (9). Suppose first that s t is the unique neighbor of v 0 in S. By (9), it follows that w 0 has a unique neighbor s w in S and s w ̸ = s t . Let H 3 be the hole given by H 3 = v 0 -r ℓ -R-q 1 -Q-q k -S-s t -v 0 . It holds that w 0 has three pairwise non-adjacent neighbors v 0 , s w , r w in H 3 , so (H 3 , w 0 ) is a proper wheel. But now by Lemma 5.4, w 0 is the center of a star cutset in G, contradicting (5).
Therefore, s t is the unique neighbor of w 0 in S. By (9), it follows that v 0 has a unique neighbor s v in S and s v ̸ = s t . Let H 4 be the hole given by H 4 = v 0 -s v -S-q k -Q-q 1 -R-r w -w 0 -v 0 . It follows that (H 4 , v) is a wheel and v has k neighbors in H 4 . Next, let H 5 be the hole given by H 5 = v 0 -s v -S-q k -Q-q 1 -R-r ℓ -v 0 . It follows that (H 5 , v) is a wheel and v has k -1 neighbors in H 5 . Since k and k -1 have different parities, it follows that one of (H 4 , v) and (H 5 , v) is an even wheel, contradicting Lemma 5.3. This completes the proof of the lemma.
Finally, we apply the previous lemma to the class of graphs with no even hole and no sector wheel. Recall that a sector wheel is a wheel (H, w) such that N (w) ∩ H is a path. Theorem 5.8. Let G be minimal non-weakly FPE with no even hole and no sector wheel. Then, G has no star cutset.
Proof. Assume for contradiction that G has a star cutset. Let v ∈ V (G) be such that there exists a cutset X ⊆ N [v] of G with v ∈ X. By Lemma 5.7, v is not the center of a full star cutset of G. This fact, together with Lemma 5.1, implies that there is exactly one component C of G \ N [v]. Let A be a connected component of G \ X such that A is anticomplete to C. Then A ⊆ N (v). Since v is the center of a star cutset, it follows that A ̸ = ∅. Let B = N (C) ∩ N (A). Since C is a connected component of G \ N [v], it follows that N (C) ⊆ N (v), and so B ⊆ N (v). Also, note that B can be empty. Suppose there exist b 1 , b 2 ∈ B such that b 1 is non-adjacent to b 2 . Let P 1 be a path from b 1 to b 2 with P * 1 ⊆ C and let P 2 be a path from b 1 to b 2 with P * 2 ⊆ A. Now, P 1 ∪ P 2 is a hole and v is complete to P 2 and anticomplete to P * 1 , so (P 1 ∪ P 2 , v) is a sector wheel, a contradiction. Therefore, B is a clique. Since B = N (C) ∩ N (A), it follows that {v} ∪ B separates A from C, so {v} ∪ B is a clique cutset of G. But by Lemma 4.2, G has no clique cutset, a contradiction. This completes the proof of the theorem.