Vertex-critical co-gem-free graphs
June 10, 2026
Abstract
A graph \(G\) is \(k\)-colorable if \(V(G)\) can be partitioned into at most \(k\) stable sets. A graph \(G\) is \(k\)-chromatic if \(k\) is the smallest integer for which \(G\) is \(k\)-colorable. In general, for a fixed \(k\ge 3\), determining whether an arbitrary graph \(G\) is \(k\)-colorable is NP-complete. Consequently, \(k\)-coloring algorithms for restricted graph classes, such as \(\mathcal{H}\)-free graphs, have been widely studied over the past few decades. A graph \(G\) is \(k\)-vertex-critical if \(G\) is \(k\)-chromatic and every proper induced subgraph of \(G\) is (\(k\)-1)-colorable. Given a graph \(G\), most of the certifying \(k\)-coloring algorithms in the literature either output a \(k\)-coloring of \(G\) or a (\(k\)+1)-vertex-critical induced subgraph of \(G\), thus, proving that \(G\) is not \(k\)-colorable. As a result, \(k\)-vertex-critical graphs have gathered considerable attention in the recent years. Beaton and Cameron [Vertex-critical graphs in co-gem-free graphs, Theoretical Computer Science 1042 (2025) 115234] asked for which graphs \(H\) of order five are there finitely many \(k\)-vertex-critical (co-gem, \(H\))-free graphs for all \(k\)?
In this paper we explore the structure of (co-gem, house)-free graphs and (co-gem, dart)-free graphs, and prove that, for each \(k\ge 1\), there are finitely many \(k\)-vertex-critical (co-gem, \(H\))-free graphs, when \(H\) is in \(\{\)house, dart\(\}\).
1 Introduction↩︎
All graphs considered here are simple graphs (no loops or multiple edges). For a graph \(G\), we use \(V(G)\) and \(E(G)\) to denote the vertex-set and the edge-set of \(G\), respectively. We use [\(k\)] to denote the set \(\{1,2,\ldots,k\}\). For any missing notation and terminology we refer to [1]. A \(k\)-coloring of a graph \(G\) is a function from \(V(G)\) to the set of “colors" [\(k\)] such that any two adjacent vertices receive different colors. A \(k\)-coloring of a graph \(G\) can also be viewed as a partition of \(V(G)\) into at most \(k\) stable sets. The smallest integer for which \(G\) is \(k\)-colorable is called the chromatic number of \(G\), and is denoted by \(\chi(G)\). Coloring has been well studied in the literature due to its various applications; see [2]. A \(k\)-chromatic graph \(G\) is \(k\)-critical if every proper subgraph of \(G\) is (\(k\)-1)-colorable, and is \(k\)-vertex-critical if every proper induced subgraph of \(G\) is (\(k\)-1)-colorable. For a graph \(H\), a graph \(G\) is \(H\)-free if no induced subgraph of \(G\) is isomorphic to \(H\), and for a set of graphs \(\mathcal{H}\), \(G\) is \(\mathcal{H}\)-free if \(G\) is \(H\)-free for all graphs \(H\) in \(\mathcal{H}\).
Given a graph \(G\), if \(G\) is \(k\)-chromatic then it will contain an induced subgraph which is \(k\)-vertex-critical. On the other hand, if a graph \(G\in \mathcal{G}\) is not \(k\)-colorable it must contain an \(m\)-vertex-critical graph belonging to \(\mathcal{G}\) for some \(m > k\). Thus, studying the structure of \(k\)-vertex-critical graphs of a graph class \(\mathcal{G}\) might explain why certain graphs in \(\mathcal{G}\) need more than (\(k\)-1)-colors to color its vertices. For a fixed integer \(k\ge 3\), the problem of deciding whether an arbitrary graph \(G\) is \(k\)-colorable is well-known to be NP-complete [3]. This led many researchers to study \(k\)-coloring in restricted graph classes, such as \(\mathcal{H}\)-free graphs. The \(H\)-free coloring problem asks: For an \(H\)-free graph \(G\), find the chromatic number of \(G\). In [4], it was proved that the \(H\)-free coloring problem can be solved in polynomial-time if \(H\) is an induced subgraph of \(P_3\)+\(P_1\) or \(P_4\), and is NP-hard for all other \(H\). This implies that \(P_5\)-free coloring problem and co-gem-free coloring problem is NP-hard. However, for a fixed \(k\), one can decide if a graph \(G\) is \(k\)-colorable when \(G\) is (\(P_5\)+\(\ell P_1\))-free where \(\ell\ge 0\), see [5], [6]. Interestingly, if one can show that, for a fixed \(k\ge 1\), there are finitely many \((k+1)\)-vertex-critical \(H\)-free graphs, then determining if an \(H\)-free graph is \(k\)-colorable becomes polynomial-time solvable.
Theorem 1 (folklore). For a fixed \(k\ge 1\), if there are finitely many \(k\)-vertex-critical \(\mathcal{H}\)-free graphs, then there is a polynomial-time algorithm to determine whether \(G\in \mathcal{H}\) is \(k\)-colorable.
Using the result mentioned above, for some restricted graph classes, one can obtain a polynomial-time certifying algorithm to determine if a graph is \(k\)-colorable for a fixed \(k\). An algorithm is said to be certifying if it returns a certificate of correctness, with each output, that can be verified in polynomial time (for a survey, see[7]). A certifying algorithm for determining if a graph \(G\) is \(k\)-colorable can output a \(k\)-coloring of \(G\) when it is an “yes" instance or output a (\(k\)+1)-vertex-critical induced subgraph of \(G\) when it is a”no" instance. The polynomial-time algorithm for determining \(k\)-colorability of a \(P_5\)-free graph given in [8], and for a (\(P_5+\ell P_1\))-free graph given in [5] are not certifying. Thus, the problem of determining the number of \(k\)-vertex-critical graphs in a graph class has gathered much attention in the past decade, specifically for \(P_5\)-free graphs and for (\(P_4\)+\(\ell P_1\))-free graphs. Following [9], we call it the Finiteness Problem.
Problem 1 (Finiteness Problem). Given a hereditary class of graphs \(\mathcal{G}\) and an integer \(k\), are there a finite number of \(k\)-vertex-critical graphs in \(\mathcal{G}\)?
In this paper we will focus on those graph classes which can be defined by forbidden induced subgraph. Note that, co-graphs (\(P_4\)-free graphs) are perfect and hence, the only \(k\)-vertex-critical co-graph is the complete graph on \(k\) vertices. For a graph \(H\) and for \(k\le 4\), the above problem has been completely solved for \(H\)-free graphs by Chudnovsky et. al. [10], [11]. They proved that there are finitely many 4-vertex-critical \(H\)-free graphs if and only if \(H\) is an induced subgraph of one of the graphs in (2\(P_3\), \(P_6\), \(P_4\)+\(\ell P_1\)) for some \(\ell\ge\) 0. On the other hand, for \(k\ge 5\) and for a graph \(H\), the only open case of Problem 1 for \(H\)-free graphs is when \(H\) is \(P_4\)+\(\ell P_1\) for some \(\ell\ge\) 1 (see [12]–[14]). In [14], it was proved that for \(k\ge 5\) there are infinitely many \(k\)-vertex-critical \(P_5\)-free graphs. This led several researchers to study Problem 1 for (\(P_5\), \(H\))-free graphs. For more results on (\(P_5\), \(H\))-free graphs we refer the reader to [9], [15]–[22] and the references therein.
In [23], Goedgebeur and Schaudt gave an exhaustive algorithm to generate all \(k\)-vertex-critical \(\mathcal{H}\)-free graphs, where \(\mathcal{H}\) is a set of graphs. Although there is no guarantee that the algorithm will terminate, several researchers have used this algorithm to generate all \(k\)-vertex-critical graphs for small \(k\) for some \(\mathcal{H}\)-free graphs (for example, see [20], [22], [24]).
In [25], [26], Beaton and Cameron have studied vertex-critical (co-gem, \(H\))-free graphs. When \(H\) is any graph on four vertices, they proved that for all \(k\ge 1\) there are finitely many \(k\)-vertex-critical (co-gem, \(H\))-free graphs. Also, when \(H\) is one of the graph in \(\{\) paw\(+K_1\), chair\(\}\), they proved that for all \(k\ge 1\) there are finitely many \(k\)-vertex-critical (co-gem, \(H\))-free graphs. They asked for which other graphs \(H\) of order five are there finitely many \(k\)-vertex-critical (co-gem, \(H\))-free graphs for all \(k\)?
Our Contribution: The purpose of this paper is to answer Problem 1 for (co-gem, house)-free graphs and (co-gem, dart)-free graphs. In Section 3, we will use a structural result on prime (co-gem, dart)-free graphs and prove the following (see Figure 1 for named graphs):
Theorem 2. For each \(k\ge 1\), the number of \(k\)-vertex-critical (co-gem, house)-free graphs is finite.
Corollary 1. For each \(k\ge 1\), there exists a polynomial-time certifying algorithm to determine whether a (co-gem, house)-free graph is \(k\)-colorable.
Later, in Section 4, we will study the structure of (co-gem, dart)-free graphs. We will prove the following result which can be of independent interest.
Lemma 1. Suppose \(H\) is a co-connected \((\)co-gem, dart, \(C_5)\)-free graph, then \(H\) is perfect or \(H\) is 3\(K_1\)-free.
We will finally prove the following.
Theorem 3. For each \(k\ge 1\), the number of \(k\)-vertex-critical \((\)co-gem, dart\()\)-free graphs is finite.
Corollary 2. For each \(k\ge 1\), there exists a polynomial-time certifying algorithm to determine whether a (co-gem, dart)-free graph is \(k\)-colorable.
2 Definitions↩︎
We use \(P_n\), \(C_n\), and \(K_n\), to denote the chordless path, the chordless cycle, and the complete graph on \(n\) vertices, respectively. For a graph \(G\), co-\(G\) (\(\overline{G}\)) denotes the complement of \(G\). A component of a graph \(G\) is a maximal connected induced subgraph of \(G\). An anti-component of a graph \(G\) is a component of co-\(G\). A graph \(G\) is co-connected if co-\(G\) is connected. A graph \(H\) is said to be a subgraph of \(G\), if \(V(H)\subseteq V(G)\) and \(E(H)\subseteq E(G)\). A subgraph of \(G\) induced by a subset \(S\subseteq V(G)\) is the subgraph of \(G\) with vertex-set \(S\) and edge-set all edges of \(G\) which have both ends in \(S\); it is denoted by \(G[S]\). A subgraph \(H\) of \(G\) is said to be proper if \(E(H) \neq E(G)\). For a subset \(S\subseteq V(G)\), we use \(G\)-\(S\) to denote the subgraph of \(G\) obtained by deleting the vertices of \(S\) from \(G\). For a vertex \(v\), we use \(G\)-\(v\) instead of \(G\)-\(\{v\}\).
Two disjoint subsets \(S_1\), \(S_2\) of \(V(G)\) are complete (resp., anticomplete) to each other if \(G\) has all possible edges (resp., no edges) between any two vertices where one is from \(S_1\) and the other is from \(S_2\). For a vertex \(v\in V(G)\), the open neighborhood of \(v\), denoted \(N(v)\), is the set of vertices in \(V(G)\setminus \{v\}\) adjacent to \(v\), and the closed neighborhood of \(v\), denoted \(N[v]\), is \(N(v)\cup \{v\}\). For a subset \(S\subseteq V(G)\), we define \(N(S):= \{u\in V(G)\setminus S\mid u \text{ has a neighbor in } S\}\), and \(N[S] := S\cup N(S)\). A hole is a graph \(C_p\) for some \(p\ge 5\); odd hole (resp., even hole) is a hole of odd length (resp., even length). For two disjoint graphs \(G\) and \(H\), \(G\)+\(H\) denote the union of two graphs with vertex-set \(V(G)\cup V(H)\) and edge-set \(E(G)\cup E(H)\). For a positive integer \(r\), we use \(rG\) to denote the graph consisting of the disjoint union of \(r\) copies of \(G\). A stable set (resp., clique) is a set of mutually nonadjacent (resp., adjacent) vertices. The clique number of a graph \(G\), denoted \(\omega(G)\), is the size of a largest clique in \(G\).
A module \(S\) of a graph \(G\) is a subset of vertices such that every vertex in \(V(G)\setminus S\) is either complete or anticomplete to \(S\). A maximal module \(S\) is said to be homogeneous (also known as non-trivial module) if \(1 < |S| < |V(G)|\). A graph is said to be prime if it does not contain any homogeneous set. A trivial prime graph is a graph with at most two vertices. Note that the smallest non-trivial prime graph is \(P_4\). For a prime graph \(G\), partitioning \(V(G)\) into maximal modules can be done in linear time [27]. By substituting a graph \(H\) for \(S\subseteq V(G)\) we mean taking the union of graphs \(G\)-\(S\) and \(H\), and adding an edge between every vertex of \(H\) and every vertex of \(G\)-\(S\) that is adjacent to some vertex of \(S\) in \(G\). A blowup of a graph \(G\) is a graph obtained from \(G\) by recursively substituting a non-empty complete graph for each vertex in \(G\). A \(k\)-vertex-critical blowup of a graph \(G\), is a blowup of \(G\) which is \(k\)-vertex-critical. Note that, for some graphs \(G\) and for some \(k\), for example graph \(G \cong P_4\) and \(k\) = 3, there is no \(k\)-vertex-critical blowup of \(G\).
3 (co-gem, house)-free graphs↩︎
A graph \(G\) is perfect if, for every induced subgraph \(H\) of \(G\), \(\chi(H)\) = \(\omega(H)\). In [28], it was proved that a graph is perfect if and only if it does not contain neither an odd hole nor its complement. See [29] for a detailed structure of prime (co-gem, house)-free graphs. The result below is obtained by combining Corollary 3.1, Lemma 4.1, and Lemma 5.1 given in [29].
Theorem 4 ([29]). Suppose \(G\) is a (co-gem, house)-free graph, then one of the
following holds.
\(\bullet\) \(G\) has a homogeneous set, or
\(\bullet\) \(G\) is a specific graph with at most 9 vertices, or
\(\bullet\) \(G\) is perfect, or
\(\bullet\) \(V(G)\) can be partitioned into three sets \(C\), \(U\), and \(A\), where
\(C\) = \((u_1\), \(u_2\), \(u_3\), \(u_4\), \(u_5)\)
induces a \(C_5\) with edges \(u_{i}u_{i+1}\) \((i\) mod 5\()\), \(U\) is a clique complete
to \(C\), and \(A\) induces a \(P_4\)-free graph where every vertex is adjacent to exactly the same two vertices \(u_{i}\)
and \(u_{i+1}\) of \(C\) (\(i\) mod 5).
Lemma 2 ([22]). Let \(G\) be a \(k\)-vertex-critical graph and \(S\) be a homogeneous set of V(G). For each component \(A\) of \(G[S]\), if \(\chi(A) = m\) with \(m < k\), then \(A\) is an \(m\)-vertex-critical graph.
Theorem 5 ([15]). Suppose \(\mathcal{G}\) is a hereditary class of graphs. For all positive integer \(k\), if the number of vertices in each \(k\)-vertex-critical blowup of every prime graph in \(\mathcal{G}\) is bounded by a constant, then the number of vertices in each \(k\)-vertex-critical graph in \(\mathcal{G}\) is bounded by a constant.
A clique cutset of a graph \(G\) is a clique, say \(Q\), in \(G\) such that \(G\)-\(Q\) has more components than \(G\). We are now ready to prove Theorem 2, which states that “For each \(k\ge 1\), the number of \(k\)-vertex-critical (co-gem, house)-free graphs is finite".
Proof of Theorem 2. We shall prove that for each \(k\ge 1\), the number of vertices in a \(k\)-vertex-critical (co-gem, house)-free graph is bounded by a constant. From Theorem 5, it is sufficient to prove that the number of vertices in each \(k\)-vertex-critical blowup of every prime graph in \(\mathcal{G}\) is bounded by a constant. Let \(\mathcal{C}(i)\) denote the upper bound on the number of vertices of an \(i\)-vertex-critical blowup of a prime (co-gem, house)-free graph. The proof is by induction on \(k\).
Let \(G\) be an arbitrary prime (co-gem, house)-free graph, and let \(H\) be a \(k\)-vertex-critical blowup of \(G\). We show that \(|V(H)|\) is bounded. If \(G\) is perfect, then so is \(H\) [30], thus \(H\) has \(k\) vertices. So we assume \(G\) is not perfect. Since \(G\) does not have a homogeneous set, from Theorem 4, (i) \(G\) is a specific graph with at most nine vertices, or (ii) \(V(G)\) can be partitioned into three sets \(C\), \(U\), and \(A\), where \(C\) = (\(u_1\), \(u_2\), \(u_3\), \(u_4\), \(u_5\)) induces a \(C_5\) with edges \(u_{i}u_{i+1}\) (\(i\) mod 5), \(U\) is a clique complete to \(C\), and \(A\) induces a \(P_4\)-free graph where every vertex is adjacent to exactly the same two vertices \(u_{i}\) and \(u_{i+1}\) of \(C\) (\(i\) mod 5).
Note that, since \(H\) (which is \(k\)-vertex-critical) is obtained from \(G\) by recursively substituting a clique of size at most \(k\)-1, \(|V(H)|\le |V(G)|\times (k-1)\). Therefore, if \(G\) is a specific graph with at most nine vertices, then \(|V(H)|\le 9\times (k-1)\).
Suppose \(V(G)\) can be partitioned into three sets \(C\), \(U\), and \(A\) as explained above, then \(\{u_i, u_{i+1}\}\cup U\) is a clique cutset in \(G\). This implies that \(H\) also has a clique cutset since each vertex in \(G\) is substituted by a clique to obtain \(H\). Since a \(k\)-vertex-critical graph does not have clique cutsets [31], this contradicts that \(G\) is a \(k\)-vertex-critical graph. ◻
4 (co-gem, dart)-free graphs↩︎
We shall first prove a simple result on the structure of prime \((\)co-gem, dart\()\)-free graphs.
Lemma 3. Suppose \(G\) is a prime \((\)co-gem, dart\()\)-free graph, then \(G\) is \(H_1\)-free.
Proof. Let \(G\) be a prime (co-gem, dart)-free graph. Assume \(G\) contains \(H_1\) induced by \(W\) = \(\{a_1,a_2,b_1,b_2,b_3,b_4\}\) such that \(\{b_1a_1, b_1a_2, b_1b_2, a_1a_2, a_1b_3, a_2b_3, b_2b_3, b_3b_4\}\subseteq E(G)\). Since \(\{a_1,a_2\}\) is not a homogeneous set, there exists a vertex \(v\in (V(G)\setminus W)\) adjacent to \(a_1\) but not to \(a_2\). Since \(\{b_1,a_2,b_3,a_1,v\}\) does not induce a dart, \(v\) must be adjacent to \(b_1\) or \(b_3\). Moreover, \(vb_2\in E(G)\), for otherwise, \(\{a_2,a_1,v,b_1,b_2\}\) or \(\{a_2,a_1,v,b_3,b_2\}\) induces a dart, a contradiction. Furthermore, \(vb_4\in E(G)\); for otherwise \(\{a_2,a_1,v,b_2,b_4\}\) induces a co-gem, a contradiction.
Now, if \(vb_1\in E(G)\), then \(\{a_1,b_1,b_2,v,b_4\}\) induces a dart, and if \(vb_3\in E(G)\), then \(\{b_2\), \(v\), \(b_4\), \(b_3\), \(a_2\}\), induces a dart, a contradiction. Thus, we conclude \(G\) is \(H_1\)-free. ◻
Let \(G\) be a prime (co-gem, dart)-free graph. Suppose \(G\) contains an induced \(C_5\), induced by the set, say \(C:= \{v_1, v_2, v_3, v_4, v_5\}\) where \(v_iv_{i+1}\in E(G)\) for \(i\) modulo 5. We define the following the sets (all indices are considered modulo 5):
| \(V_i\) | := | \(\{u \in V(G) \mid N(u) \cap C = \{v_{i-1}, v_{i+1}\}\text{ or } \{v_{i-1},v_i,v_{i+1}\}\}\), |
| \(A_i\) | := | \(\{u \in V(G)\setminus C \mid N(u) \cap C = \{v_i, v_{i+1}\}\}\), |
| \(B_i\) | := | \(\{u \in V(G)\setminus C\mid N(u) \cap C = \{v_i, v_{i+2}, v_{i-2}\}\}\), |
| \(D_i\) | := | \(\{u \in V(G)\setminus C\mid N(u) \cap C = C\setminus \{v_i\}\}\), and |
| \(U\) | := | \(\{u \in V(G)\setminus C \mid N(u) \cap C = C\}\). |
Note that \(v_i\in V_i\) for all \(i\in [5]\). Let \(A:= \cup_{i=1}^{5} A_i\), \(B:=\cup_{i=1}^{5} B_i\), and \(D:= \cup_{i=1}^{5} D_i\). Then since \(G\) does not contain a co-gem, it is not difficult to see that \(V(G)\) = (\(\cup_{i=1}^{5} V_i) \cup A\cup B\cup D \cup U\). We shall first prove some properties (all indices are taken modulo 5).
\(V_i\) is either a stable set or a clique.
It is enough to show that \(G[V_i]\) is (\(P_3\), \(K_2\)+\(K_1\))-free. Suppose not, if \(G[V_i]\) contains an induced \(P_3\), say with vertex-set \(W\), then \(W\cup \{v_{i+1},v_{i+2}\}\) induces a dart, a contradiction, and if \(G[V_i]\) contains an induced \(K_2\)+\(K_1\), say with vertex-set \(W'\), then \(W'\cup \{v_{i-1}, v_{i+1}, v_{i+2}\}\) induces an \(H_1\), a contradiction to Lemma 3.
Sets \(A_i\), \(B_i\), and \(D_i\) are cliques.
Suppose \(x\) and \(y\) are nonadjacent. If \(x,~y\in A_i\), then \(\{x,v_i,y,v_{i+1},v_{i+2}\}\) induces a dart, a contradiction. If \(x,~ y\in B_i\), then \(\{x,v_{i+2},y,v_{i+3},v_{i+1}\}\) induces a dart, a contradiction. If \(x,~ y\in D_i\), then \(\{x,v_{i+2},y,v_{i+1},v_i\}\) induces a dart, a contradiction.
\(U\) is anticomplete to \(A\), and if \(U\) is not empty, then \(B\) is empty.
Let \(u\in U\). Suppose \(a\in A_i\) is adjacent to \(u\), then \(\{a,v_{i+1},v_{i+2},u,v_{i-1}\}\) induces a dart, a contradiction. Suppose \(b\in B_i\), then \(\{v_{i-1},u,v_{i+1},v_i,b\}\) or \(\{v_{i+1}, v_{i+2},b,u,v_{i-1}\}\) induces a dart, a contradiction.
If \(U\neq \emptyset\), then \(V_i\) is a clique.
Let \(u\in U\). From [item-Vi], it is sufficient to show that each vertex \(x\in V_i\) is adjacent to \(v_i\). Suppose \(x\) is not adjacent to \(v_i\), then \(\{v_i, u, v_{i+2}, v_{i+1}, x\}\) or \(\{x,v_{i+1},v_{i},u,v_{i+3}\}\) induces a dart, a contradiction.
Suppose \(x\), \(y\) are two nonadjacent vertices in \(U\), then any vertex \(z\in V_i\cup D_i\) is adjacent to at least one of the vertices \(x\), \(y\).
Due to symmetry we only prove for \(i\) = 1. Suppose \(z\in V_1\cup D_1\) is anticomplete to \(\{x,y\} \subseteq U\), then \(z\neq v_1\), and \(\{x,v_3,y,v_2,z\}\) or \(\{x,v_1,y,v_2,z\}\) induces a dart, a contradiction.
Suppose \(V_i\) is a stable set, then \(V_i\) is complete to \(V_{i-1}\cup V_{i+1}\) and is anticomplete to \(V_{i-2}\cup V_{i+2}\).
Let \(u\in V_1\) be not adjacent to \(v_1\). Due to symmetry, it is sufficient to prove that \(u\) is anticomplete to \(V_3\) and is complete to \(V_2\). Suppose \(x\in V_3\) is adjacent to \(u\), then \(\{u,x,v_4,v_3,v_1\}\) induces a co-gem or \(\{u,x,v_3,v_2,v_1\}\) induces a dart, a contradiction. Suppose \(y\in V_2\) is not adjacent to \(u\), then \(\{u,v_2,v_1,y,v_4\}\) induces a co-gem or \(\{v_1,y,v_3,v_2,u\}\) induces a dart, a contradiction.
The following lemma is a slight modification of the Lemma 4 in [22], we give proof here for completeness.
Lemma 4. Suppose \(G\) is a dart-free graph. Let \(S\) and \(T\) be two disjoint subsets of \(V(G)\) such that \(|S|\) is bounded, \(S\) is not complete to \(T\), and \(G[T]\) is co-connected. Suppose the following conditions hold:
for any two nonadjacent pair of vertices \(x_1\), \(x_2\) in \(T\), no vertex in \(S\) is anticomplete to \(\{x_1, x_2\}\), and
there exists a vertex \(y\in V(G)\setminus (S\cup T)\) which is complete to \(S\cup T\).
Then \(|T| \leq ~ f(\chi(G[T])\).
Proof. Assume the hypotheses. Let \(N_0 := S\) and for \(i\ge 1\), let \(N_i:= \{u\in T\setminus (\bigcup_{j=1}^{i-1} N_j) \mid u \text{ has a non-neighbor in } N_{i-1}\}\). Since \(S\) is not complete to \(T\), \(N_1\neq \emptyset\). Moreover, \(T' := T\setminus(\bigcup_{j=1}^{\infty}N_j)\) is empty; for otherwise \(T'\) is complete to \(T\setminus T'\) which contradicts \(G[T]\) is co-connected. Our goal is to prove that \(|N_i|\) is bounded, for all \(i\ge 0\), and that there exists an integer \(\ell\) such that \(N_j = \emptyset\) for all \(j\ge \ell\).
Note that, by definition, for all \(i\ge 1\) each \(N_i\) is complete to \(N_l\) for all \(l\notin \{i-1,i+1\}\). Thus, if \(N_{2\chi(G[T])} \neq \emptyset\), then, for some \(v_i\in N_i\), \(\{v_0, v_2, v_4, \ldots, v_{2\chi(G[T])}\}\) induces a clique of size \(\chi(G[T])\)+1, a contradiction. Thus, \(N_j\) = \(\emptyset\) for all \(j\ge 2\chi(G[T])\).
Claim 1: For all \(i\ge 0\) and for any two nonadjacent pair of vertices \(z_1\), \(z_2\) in \(N_{i+1}\), any vertex \(v\in N_i\) is not anticomplete to \(\{z_1, z_2\}\).
The claim is true for \(i\) = 0 by our hypothesis on \(S\). Suppose the claim is not true for \(i > 0\). By definition of \(N_i\), there is a vertex, say \(v'\), in \(N_{i-1}\) nonadjacent to \(v\), and by our hypothesis, there is a vertex \(y\in V(G)\setminus (S\cup T)\) complete to \(S\cup T\). Then \(\{z_1,v',z_2,y,v\}\) induces a dart, a contradiction. \(\mathbin{\vcenter{\rule{0.75ex}{1.0ex}}}\)
Claim 2: For all \(i\ge 0\), \(|N_i|\) is bounded.
The proof is by induction on \(i\). Since \(|S|\) is bounded, say \(|S|\le c\), the claim is true for \(i\) = 0. So assume \(i\ge 1\). Note that, each \(N_i\subseteq T\) can be partitioned into at most \(\chi(G[T])\) stable sets. However, by Claim 1, any stable set of \(N_i\) can have at most one non-neighbor of \(v\), where \(v\) is any vertex in \(N_{i-1}\). Thus, any stable set of \(N_i\) can have at most \(|N_{i-1}|\) vertices. This implies that \(|N_i|\) is bounded by \(|N_{i-1}|\times \chi(G[T])\). A quick analysis using recursions will give us \(|N_i|\le c\times(\chi(G[T]))^{i-1}\). \(\mathbin{\vcenter{\rule{0.75ex}{1.0ex}}}\) ◻
Lemma 5. For each \(k\ge 1\), there are finitely many prime \(k\)-colorable \((\)co-gem, dart\()\)-free graphs containing a \(C_5\).
Proof. Let \(G\) be a \(k\)-colorable prime (co-gem, dart)-free graph. Let \(G\) contain a \(C_5\) induced by
\(C = \{v_1, v_2, v_3, v_4, v_5\}\) such that \(v_iv_{i+1}\in E(G)\) for \(i\) modulo 5. For \(i\) mod 5, we define the sets
\(V_i\), \(A_i\), \(B_i\), \(D_i\), and \(U\) as above. We show that \(|V(G)|\) is bounded.
Case 1: \(U\) is empty.
Then \(V(G)\) = \((\bigcup_{i=1}^{5} V_i) ~\cup A \cup B \cup D\). Note that, from [item-ABD-clique], the sets \(A_i\), \(B_i\), and \(D_i\) are cliques. So, we have \(|A\cup B\cup D| ~\le ~ (5k + 5k + 5k)\) = 15\(k\). Thus, it is sufficient to prove that \(|V_i|\) is bounded for all \(i\in [5]\). From [item-Vi], \(V_i\) is either a clique or a stable set. Obviously, if \(V_i\) is a clique, then \(|V_i|\le k\); so we assume that \(V_i\) is a stable set.
From [item-Vistable], no vertex in \((\bigcup_{j=1}^{5} V_j)\setminus V_i\) is mixed on two vertices of \(V_i\). Thus, since \(G\) is prime, for any two vertices, say \(x\) and \(y\), in \(V_i\), \(N(x)\cap (A\cup B\cup D) \neq N(y)\cap (A\cup B\cup D)\); for otherwise \(N(x)\) = \(N(y)\) and \(\{x,y\}\) is a homogeneous
set, a contradiction. However, since \(|A\cup B\cup D|\leq ~15k\), if \(|V_i|> ~ 2^{15k}\), then by the Pigeonhole Principle, there are two vertices \(p\)
and \(q\) in \(V_i\) such that \(N(p)\) = \(N(q)\), which contradicts that \(G\) is prime.
Therefore, we conclude that \(|V_i|\leq ~2^{15k}\); so \(|V(G)| \leq ~(5\times2^{15k}) + 15k\), and we are done.
Case 2: \(U\) is not empty.
Then \(V(G)\) = \((\bigcup_{i=1}^{5} V_i) ~\cup A \cup D \cup U\) by [item-U]. From [item-ABD-clique], and [item-UV], the sets \(A_i\), \(D_i\), and \(V_i\) are cliques; so we have \(|V(G)\setminus U|\leq (5k+5k+5k)\). Thus, it is sufficient to prove that \(|U|\) is bounded. Note that, since \(G[U]\) is \((k-3)\)-colorable, there can be at most \(k-3\) anti-components in \(G[U]\). So we will show that any arbitrary anti-component, say induced by \(T\), of \(G[U]\) has bounded number of vertices. Note, from [item-U], \(U\) is anticomplete to \(A\). Suppose, for all \(i\in [5]\), no vertex in \(V_i \cup D_i\) is mixed on \(T\), then \(T\) is a homogeneous set when \(|T|\ge 2\), and thus \(|T|\) = 1. So we assume there is a vertex, say \(s\), in \(V_i\cup D_i\), for some \(i\in [5]\), which is mixed on \(T\). Let \(S\) = \(\{s\}\) and let \(w\) = \(v_{i+1}\). Note that since \(s\) is mixed on \(T\) and \(G[T]\) is co-connected, we conclude that \(G[S\cup T]\) is also co-connected. Thus, from [item-compare] and from Lemma 4, it follows that \(|T|\) is bounded. ◻
We shall now prove Lemma 1, which states that “Suppose \(H\) is a co-connected \((\)co-gem, dart, \(C_5)\)-free graph, then \(H\) is perfect or \(H\) is 3\(K_1\)-free".
Proof of Lemma 1. Assume the hypothesis. Note that, since \(H\) is (co-gem, \(C_5\))-free, if \(H\) is not perfect, then \(H\) contains a co-\(C_{2p+1}\) for some \(p\ge 3\). So it is sufficient to prove that every co-connected \((\)co-gem, dart, \(C_5)\)-free graph containing a \(C_{2p+1}\), for some \(p\ge 3\), is 3\(K_1\)-free. We will prove the complement, i.e., we will prove that every connected (gem, co-dart, \(C_5\))-free graph containing a \(C_{2p+1}\), for some \(p\ge 3\), is triangle-free.
Let \(G\) be a connected (gem, co-dart, \(C_5\))-free graph which contains an odd hole of length 2\(p\)+1 for some \(p\ge
3\). Let \(C\) = \(\{v_1,v_2,\dots, v_{2p+1}\}\) such that \(v_iv_{i+1}\in E(G)\), for all \(i\) mod 2\(p\)+1, be a smallest odd hole in \(G\). For all \(i\) mod 2\(p\)+1, we claim the following.
Claim 1: The set \(N(v_i)\cap N(v_{i+1})\) is empty.
Due to symmetry, we will prove for \(i\) = 1. Suppose \(x\in N(v_1)\cap N(v_2)\). Since \(G\) is gem-free \(x\) cannot be
complete to \(\{v_3,v_{2p+1}\}\), without loss of generality, assume \(x\) is not adjacent to \(v_{2p+1}\). Suppose \(x\) is
not adjacent to \(v_{2p-1}\) (resp., \(v_{2p-2}\)), then \(\{x,v_2,v_1,v_{2p+1},v_{2p-1}\}\) (resp., \(\{x,v_2,v_1,v_{2p+1},v_{2p-2}\}\)) induces a co-dart, a contradiction. Then \(\{v_{2p-1},v_{2p-2},x,v_2,v_{2p+1}\}\) induces a co-dart, a contradiction. \(\mathbin{\vcenter{\rule{0.75ex}{1.0ex}}}\)
Claim 2: For every \(x\in N(C)\), \(N(x) \cap C \subseteq \{v_j, v_{j+2}\}\) for some \(j\) mod 2\(p\)+1.
Suppose \(x\in N(C)\). Note that \(G[C]-v_j\) is an induced path of even length. From Claim 1, \(x\) cannot be adjacent to two consecutive vertices of
\(C\). Thus, removing each additional vertex in \(N(x)\cap C\) from \(G[C]-v_j\) splits this even length path into two disjoint paths of different parity. So
we can conclude that, \(G[C\setminus N(x)]\) always has an induced path of even length, say \(P\). If \(N(x)\) is not one of the sets \(\{v_j\}\), \(\{v_{j-2}, v_j\}\), or \(\{v_j, v_{j+2}\}\), then \(P\cup \{x\}\) induces an odd hole of length less than 2\(p\)+1, a contradiction to the choice of \(C\). \(\mathbin{\vcenter{\rule{0.75ex}{1.0ex}}}\)
Claim 3: \(G[C\cup N(C)]\) is triangle-free.
Let \(T_0 = \{x,y,z\} \subseteq (C \cup N(C))\) induces a triangle. From Claims 1 and 2, at least two vertices of \(T_0\) must be from \(N(C)\). Suppose \(x\in C\) and \(y,z \in N(C)\); without loss of generality, let \(x\) = \(v_1\). Then, from Claim 2, \(\{y,z,x,v_{2p+1}, v_4\}\) induces a co-dart, a contradiction. Thus \(T_0 \subseteq N(C)\), and no two vertices in \(T_0\) have same neighbor in \(C\). From Claim 2, each vertex in \(N(C)\) can have at most two neighbors in \(C\). So, there is a vertex, say \(u\), in \(C\) which is anticomplete to \(\{x,y,z\}\). Moreover, since \(C\) induces a cycle and no two vertices in \(T_0\) have same neighbor in \(C\), there is a vertex in \(N(T_0)\cap C\), say \(w\), not adjacent to \(u\). Then \(\{x,y,z,w,u\}\) induces a co-dart, a contradiction. \(\mathbin{\vcenter{\rule{0.75ex}{1.0ex}}}\)
Let \(N_0 := C\), and for all \(i\ge 1\), \(N_i := \{v\in V(G)\setminus (\bigcup_{j=0}^{i-1} N_j) ~\mid ~ v\) has a neighbor in \(N_{i-1}\}\). Note \(N_1 = N(C)\).
Claim 4: For all \(j\ge 0\) and for each \(v\in N_j\), \(N(v)\) is a stable set.
The proof is by induction on \(j\). From Claim 3, it is true for \(j\) = 0. Suppose for some \(v\in N_1\), there are two neighbors \(u\) and \(w\) in \(N(v)\). Then from Claim 3, \(u\) or \(w\) must be in \(N_2\). Without loss of generality, assume \(w\in N_2\) and \(v\in N(v_1)\). Then \(uv_4\in E(G)\); for otherwise, from Claim 2, \(\{v_1,v,u,w,v_4\}\) induces a co-dart, a contradiction. Now, again from Claim 2, \(\{v_4,u,v,w,v_{2p+1}\}\) induces a co-dart, a contradiction. Hence the claim is true for \(j\) = 1. If possible, let \(l \ge 2\) be the smallest integer for which the claim is not true. Then there exists \(u_1\in N_l\) such that \(u_2\), \(u_3\in N(u_1)\) are adjacent. Let \(w_1 \in N_{l-1}\) be a neighbor of \(u_1\). Then by the choice of \(l\), \(w_1\) is anticomplete to \(\{u_2, u_3\}\). Since \(l\ge 2\), from Claim 2, there is a vertex, say \(w_2 \in C\), which is not adjacent to \(w_1\). Then we see that \(\{u_1,u_2,u_3,w_1,w_2\}\) induces a co-dart, a contradiction. \(\mathbin{\vcenter{\rule{0.75ex}{1.0ex}}}\)
Since \(G\) is connected the result follows from Claim 4. ◻
We are now ready to prove Theorem 3, which states that “For each \(k\ge 1\), the number of \(k\)-vertex-critical \((\)co-gem, dart\()\)-free graphs is finite".
Proof of Theorem 3. From Theorem 5, it is sufficient to prove that, for each \(k\ge 1\), the number of vertices in each \(k\)-vertex-critical blowup of any prime graph in \(\mathcal{G}\) is bounded by a constant. The proof is by induction on \(k\).
Let \(G\) be a prime (co-gem, dart)-free graph. If \(G\) is perfect, then the only \(k\)-vertex-critical blowup of \(G\) is the complete graph on \(k\) vertices. So we assume \(G\) is not perfect. Since \(G\) is co-gem-free it must contain a \(C_5\) or a co-\(C_{2p+1}\), for some \(p\ge 3\). If \(G\) is \(C_5\)-free, then from Lemma 4 \(G\) is 3\(K_1\)-free. Note that blowup of a 3\(K_1\)-free graph is also 3\(K_1\)-free. Thus, if \(G\) is 3\(K_1\)-free, then the number of vertices in each \(k\)-vertex-critical blowup of \(G\) is bounded by Ramsey number \(R(3,k+1)\).
Now we assume \(G\) contains a \(C_5\). Note that \(G\) is an induced subgraph of every blowup of \(G\). Thus, if an arbitrary blowup of \(G\), say \(H\), is \(k\)-vertex-critical, then \(G\) must be \(k\)-colorable and each vertex of \(G\) can be replaced by a clique of size at most \(k-1\) to obtain \(H\). Therefore, from Lemma 5, \(|V(G)|\) is bounded, and hence \(|V(H)| \le |V(G)|\times (k-1)\) is bounded. ◻
Acknowledgment↩︎
The first author is supported by Anusandhan National Research Foundation (ANRF), Govt. of India, under the National Postdoctoral Fellowship (NPDF) program (No. PDF/2025/005208), and the second author is supported by the National Board of Higher Mathematics (NBHM), DAE, India (No. 02011/55/2023 NBHM (R. P)/R&D II/16733).
References↩︎
Computer Science Unit, Indian Statistical Institute, Chennai Centre, Nelson Manickam Road, Chennai, Tamilnadu, India - 600029. Emails: mbelavadi@isichennai.res.in, karthick@isichennai.res.in.↩︎