Infinite families of $k$ -vertex-critical ( $P_{5}$ , $C_{5}$ )-free graphs

Ben Cameron
Chính T. Hoàng

Abstract

A graph is $k$ -vertex-critical if $\chi(G)=k$ but $\chi(G-v)<k$ for all $v\in V(G)$ . We construct a new infinite families of $k$ -vertex-critical $(P_{5},C_{5})$ -free graphs for all $k\geq 6$ . Our construction generalizes known constructions for $4$ -vertex-critical $P_{7}$ -free graphs and $5$ -vertex-critical $P_{5}$ -free graphs and is in contrast to the fact that there are only finitely many $5$ -vertex-critical $(P_{5},C_{5})$ -free graphs. In fact, our construction is actually even more well-structured, being $(2P_{2},K_{3}+P_{1},C_{5})$ -free.

1 Introduction

For a given integer $k$ , the $k$ -Colouring problem is to determine whether a given graph is $k$ -colourable. This problem is known to be NP-complete for all $k\geq 3$ [23] which led to tremendous interest in restricting the structure of input graphs such that polynomial-time $k$ -Colouring algorithms can be developed. One of the most popular structural restrictions is to forbid an induced subgraph. Yet, for every graph $H$ that contains an induced cycle [21] or claw [24, 17], it remains NP-complete to solve $k$ -Colouring on $H$ -free graphs for all $k\geq 3$ . Thus, assuming P $\neq$ NP, if $k$ -Colouring can be solved in polynomial time for $H$ -free graphs for $k\geq 3$ , $H$ must be a linear forest, that is, a disjoint union of paths.

To this end, it was shown that $k$ -Colouring can be solved in polynomial-time for $P_{5}$ -free graphs for all $k$ [15]. Further, $4$ -Colouring $P_{6}$ -free graphs [11, 12, 13] and $3$ -Colouring $P_{7}$ -free graphs [2] can also be solved in polynomial-time. However, solving $k$ -Colouring of $P_{t}$ -free graphs remains NP-complete if $t\geq 7$ and $k\geq 4$ or $t=6$ and $k\geq 5$ [18]. The complexity remains an open question for $P_{t}$ -free when $t\geq 8$ .

The fact that $P_{5}$ is the largest connected subgraph that can be forbidden such that $k$ -Colouring can be solved in polynomial-time for all $k$ (again assuming P $\neq$ NP) has generated special interest in further properties of $P_{5}$ -free graphs. One such property is determining which subfamilies of $P_{5}$ -free graphs admit polynomial-time certifying $k$ -Colouring algorithms. An algorithm is certifying if it returns a simple and easily verifiable witness with each output. The $k$ -Colouring algorithms for $P_{5}$ -free graphs developed in [15] return $k$ -colourings of the input graph in the case that the graph is $k$ -colourable, but there is no certificate when the graph is not $k$ -colourable. In general, a $k$ -Colouring algorithm can return a $(k+1)$ -vertex-critical induced subgraph to certify negative outputs. In fact, when the set of $(k+1)$ -vertex-critical graphs in a given family of graphs is finite, then there exists a polynomial-time certifying $k$ -Coloring algorithm for that family (see, for example, [5]).

For $k$ -vertex-critical $P_{5}$ -free graphs, it is known that there are only finitely many for $k=4$ [16] and this finite list was used to develop a linear-time $3$ -Colouring algorithm for $P_{5}$ -free graphs [26]. For $k\geq 5$ , however, there are infinitely many $k$ -vertex-critical $P_{5}$ -free graphs [16]. Thus, the search for subfamilies of $P_{5}$ -free graphs admitting polynomial-time certifying $k$ -Coloruing algorithms for $k\geq 4$ has turned to graphs that are $P_{5}$ -free and $H$ -free for other graphs $H$ . We call these graphs $(P_{5},H)$ -free. The most comprehensive result to date on $k$ -vertex-critical $(P_{5},H)$ -free graphs is the dichotomy theorem from [8] that there are only finitely many for all $k$ if and only if $H$ is not $2P_{2}$ or $K_{3}+P_{1}$ . It is further known that there are only finitely many $5$ -vertex-critical $(P_{5},H)$ -free graphs when $H$ is any of:

•

chair [20];
•

bull [19];
•

$C_{5}$ [16].

For the above graphs, the cardinality of $k$ -vertex-critical graphs remains unknown for all $k\geq 6$ .

On the infinite side, there are only two known constructions of $H$ -free graphs where $H$ is a linear forest:

•

$G_{r}$ is $4$ -vertex-critical $P_{7}$ -free for all $r\geq 1$ [9], and
•

$G_{p}$ is $5$ -vertex-critical $P_{5}$ -free for all $p\geq 1$ (in fact, $(2P_{2},K_{3}+P_{1})$ -free) [16].

These two families turn out to be special cases of the new infinite families of $k$ -vertex-critical $(P_{5},C_{5})$ -free graphs for each $k\geq 6$ that we will construct in this paper. Our families are the first defined by forbidden induced subgraphs where the boundary between only finitely many and infinitely many $k$ -vertex-critical graphs is $k=6$ (all others happen at $k\leq 5$ ). In light of the Strong Perfect Graph Theorem [10], our result is somewhat surprising as every non-complete $P_{5}$ -free $k$ -vertex-critical graph must contain $C_{5}$ or $\overline{C_{2k+1}}$ for some $k\geq 3$ . In addition, our result makes progress toward an open problem posed in [8] to find a dichotomy theorem for the number of $k$ -vertex-critical $(P_{5},H)$ -free graphs for all $k$ when $H$ is of order $5$ . To see the state-of-the-art on this problem, see Table LABEL:tab:order5suvery.

We provide our infinite families of vertex-critical graphs in Section 2. Following that we provide a large table summarizing whether there are only finitely many or infinitely many $k$ -vertex-critical $(P_{5},H)$ -free graphs for all $k$ in Section 3. From this, we find that there are only $12$ such graphs $H$ remaining to get the complete dichotomy to solve the open problem from [8]. We end this section with a brief section on notations and definitions.

1.1 Notation and Definitions

Let $\chi(G)$ denote the chromatic number of $G$ . A graph $G$ is $k$ -vertex-critical if $\chi(G)=k$ and $\chi(G-v)<k$ for all $v\in V(G)$ . For $S\subseteq V(G)$ , let $G[S]$ denote the subgraph of $G$ induced by $S$ . For vertices $u,v\in V(G)$ , we write $u\sim v$ if $u$ and $v$ are adjacent and $u\nsim v$ is $u$ and $v$ are non-adjacent. For $S,T\subseteq V(G)$ , we say $S$ is complete (anti-complete) to $T$ if $s\sim t$ ( $s\nsim t$ ) for all $s\in S$ and $t\in T$ . For a $v\in V(G)$ , $N(v)$ is the open neighbourhood and denotes the set $\{u\in V(G):u\sim v\}$ and $N[v]$ is the closed neighbourhood, denoting the set $N(v)\cup\{v\}$ . For $S\subseteq V(G)$ , we say $S$ is a stable set if $u\nsim v$ for all $u,v\in S$ . For graphs $G$ and $H$ , $G+H$ denotes the disjoint union of $G$ and $H$ where $V(G+H)=V(G)\cup V(H)$ and $E(G+H)=E(G)\cup E(H)$ . A graph $G$ is $H$ -free if it does not contain any induced subgraph isomorphic to $H$ .

2 New infinite families of $k$ -vertex-critical graphs

We are now ready to give the constructions for our infinite families of vertex-critical graphs.

Definition 2.1.

Fix $q\geq 1$ and $k\geq 3$ . Let $G(q,k)$ be a graph on vertex set $\{v_{0},v_{1},...,v_{kq}\}$ where, with each integer taken modulo $kq+1$ , the neighbourhood of vertex $v_{i}$ is

\{v_{i-1},v_{i+1}\}\cup\{v_{i+kj+m}:m=2,3,...k-1\text{ and }j=0,1,...,q-1\}.

Examples to help visualize this definition can be found in Figure 1

Figure 1: The neighbourhood of

v_{0}

G(3,6)

(left) and the graph

G(3,6)

(right).

From this definition, it is clear that $\{G(q,3):q\geq 1\}=\{G_{r}:r\geq 1\}$ where $G_{r}$ is the infinite family $4$ -vertex-critical $P_{7}$ -free graph in [9] and $\{G(q,4):q\geq 1\}=\{G_{p}:p\geq 1\}$ where $G_{p}$ is the infinite family of $5$ -vertex-critical $2P_{2}$ -free graphs in [16]. Further, our new construction is very natural in the sense that $G(1,k)\cong K_{k+1}$ and $G(2,k)\cong\overline{C_{2k+1}}$ for all $k$ , which include all prototypical $(k+1)$ -vertex-critical $P_{5}$ -free graphs except $C_{5}$ from the Strong Perfect Graph Theorem [10].

For a given $q$ and $k$ and for $0\leq i\leq k-1$ , let $V_{i}=\{v_{t}:t=\ i\pmod{k}\}$ . It is clear that the $V_{i}$ ’s partition the vertex set of $G(q,k)$ .

Lemma 2.2.

For $1\leq i\leq k$ , $V_{i}$ is a stable set of $G(q,k)$ and the only edge in $V_{0}$ is $v_{0}v_{qk}$ .

Proof.

Fix $i\in\{0,1,2\ldots,qk\}$ . Since it is clear that $v_{i}\nsim v_{i+1}$ and $v_{i}\nsim v_{i-1}$ with the exception of $v_{0}\sim v_{qk}$ , we will focus on the subset of $N(v_{i})$ defined by $\{v_{i+kj+m}:m=2,3,...k-1\text{ and }j=0,1,...,q-1\}$ . Fix $m\in\{2,3,...k-1\}$ and $j=\{0,1,...,q-1\}$ . The result now follows by considering two cases to consider.

Case 1: Suppose $i+kj+m\leq qk$ . Then $i+kj+m\equiv i+m\pmod{k}$ , and since $2\leq m\leq k-1$ , $i\not\equiv i+m\pmod{k}$ . Therefore, $v_{h}\not\in N(v_{i})$ for all $h\equiv i\pmod{k}$ .

Case 2: Suppose $i+kj+m>qk$ , then $i+kj+m\equiv i+kj+m-1\pmod{qk+1}$ , which is congruent to $i+m-1\pmod{k}$ . Since $1\leq m-1\leq k-2$ , it follows that $i\not\equiv i+m-1\pmod{k}$ . Therefore, $v_{h}\not\in N(v_{i})$ for all $h\equiv i\pmod{k}$ .

∎

Lemma 2.3.

For all $k\geq 4$ and $q\geq 1$ , $G(q,k)$ is $2K_{2}$ -free.

Proof.

Let $G=G(q,k)$ and suppose $G$ is not $2K_{2}$ -free. By symmetry, we may suppose without loss of generality that $v_{0}$ belongs to an induced $2K_{2}$ . Let $v_{\ell},x,y\in V(G)$ such that $\{v_{0},v_{\ell},x,y\}$ induces a $2K_{2}$ in $G$ such that $v_{0}\sim v_{\ell}$ and $x\sim y$ . It is clear by the definition of $G$ that $N(v_{0})=\{v_{1},v_{qk}\}\cup V_{2}\cup V_{3}\cup\cdots\cup V_{k-1}$ . Therefore, if $\{x,y\}\not\subseteq(V_{0}\setminus\{v_{0},v_{qk}\})\cup V_{1}$ , then $v_{0}$ will be adjacent to $x$ or $y$ , contradicting our assumption. Further, since $x\sim y$ , we must have $\{x,y\}\subseteq(V_{0}\setminus\{v_{0},v_{qk}\})\cup(V_{1}\setminus\{v_{1}\})$ . Since both $V_{1}\setminus\{v_{1}\}$ and $V_{0}\setminus\{v_{0},v_{qk}\}$ are stable sets from Lemma 2.2, we may assume without loss of generality that $x\in V_{0}\setminus\{v_{0},v_{qk}\}$ and $y\in V_{1}\setminus\{v_{1}\}$ . There are now only three cases to consider.

Case 1: Suppose $v_{\ell}\in V_{2}\cup V_{3}\cup\cdots\cup V_{k-2}$ . Let $\ell^{\prime}=\ell\pmod{k}$ . Since $k\geq 4$ , $2\leq\ell^{\prime}\leq k-2$ . So, for $v_{hk}\in V_{0}$ where $\ell<hk\leq qk$ , we have that $hk=\ell+k(h-1)+(k-\ell^{\prime})$ . Thus, $v_{hk}\in N(v_{\ell})$ by the definition of $G$ . For $v_{hk}\in V_{0}$ where $qk<hk<\ell$ , we have that $hk=\ell^{\prime}+k(h-1)+(k-\ell^{\prime}+1)\pmod{qk+1}$ , so again $v_{hk}\in N(v_{\ell})$ . It follows that $V_{0}\subseteq N(v_{\ell})$ and, thus, $v_{\ell}\sim x$ . This contradicts our assumption on the induced $2K_{2}$ in $G$ .

Case 2: Suppose $v_{\ell}\in V_{k-1}$ . We show that $V_{k-1}\subseteq N(y)$ . Let $h\in\{0,\ldots,qk\}$ such that $y=v_{h}$ . We know that $h=1\pmod{k}$ since $y=v_{h}\in V_{1}$ . Let $h^{\prime}\in\{0,\ldots,qk\}$ such that $h^{\prime}=k-1\pmod{k}$ . If $h<h^{\prime}$ , then since $h+kj+k-2\equiv k-1\pmod{k}$ , it follows that $v_{h}\sim v_{h^{\prime}}$ . If $h^{\prime}<h$ , then since $h+kj+k-1\pmod{qk+1}\equiv k-1\pmod{k}$ , it follows that $v_{h}\sim v_{h^{\prime}}$ . Thus, $V_{k-1}\subseteq N(y)$ , and $y\sim v_{\ell}$ which again contradicts our assumption on the induced $2K_{2}$ in $G$ .

Case 3: Suppose $v_{\ell}\in\{v_{qk},v_{1}\}$ . If $v_{\ell}=v_{1}$ , then since $1+jk+m\pmod{qk+1}=1+jk+m$ for all $0\leq j\leq q-1$ and $2\leq m\leq k-1$ , we can obtain all $v_{h}$ such that $v_{h}\in V_{0}$ in the set $\{v_{1+(q-1)j+(k-1)}:j=0,1,\ldots,q-1\}\subseteq N(v_{1})$ . Also, we can obtain all $v_{h}$ such that $v_{h}\in V_{k-1}$ in the set $\{v_{1+(q-1)j+(k-2)}:j=0,1,\ldots,q-1\}\subseteq N(v_{1})$ . Thus, $x\sim v_{1}=v_{\ell}$ which contradicts our assumption on the induced $2K_{2}$ in $G$ . Similarly, for $v_{\ell}=v_{qk}$ , we get that $y\sim v_{\ell}$ which again contradicts our assumption on the induced $2K_{2}$ in $G$ .

All three cases together show that $G$ is $2K_{2}$ -free. ∎

Lemma 2.4.

For all $k\geq 4$ and $q\geq 1$ , $G(q,k)$ is $(K_{3}+P_{1})$ -free.

Proof.

Let $G=G(q,k)$ and suppose $G$ has an induced $K_{3}+P_{1}$ . By the symmetry of $G$ , we may assume that the isolated vertex in the $K_{3}+P_{1}$ is $v_{0}$ . Let $S=\{v_{0},v_{i_{1}},v_{i_{2}},v_{i_{3}}\}$ be the subset of $V(G)$ that induces the $K_{3}+P_{1}$ with $v_{0}$ the isolated vertex. Since $v_{0}$ is anticomplete with $\{v_{i_{1}},v_{i_{2}},v_{i_{3}}\}$ , it follows that $\{v_{i_{1}},v_{i_{2}},v_{i_{3}}\}\subset V_{0}\cup V_{1}\setminus\{v_{qk}\}$ . However, since $V_{0}$ and $V_{1}\setminus\{v_{qk}\}$ stable sets by Lemma 2.2, it follows that $G[V_{0}\cup V_{1}\setminus\{v_{qk}]\}$ is bipartite and therefore triangle-free. Therefore, $G$ is $(K_{3}+P_{1})$ -free. ∎

Lemma 2.5.

For all $k\geq 5$ and $q\geq 1$ , $G(q,k)$ is $C_{5}$ -free.

Proof.

Let $k\geq 5$ , $q\geq 1$ , and $G=G(q,k)$ . Suppose by way of contradiction that $G$ contains an induced $C_{5}$ . Without loss of generality suppose $v_{0}$ is on an induced $C_{5}$ in $G$ and let $\{v_{0},v_{i_{1}},v_{i_{2}},v_{i_{3}},v_{i_{4}}\}$ induce a $C_{5}$ in $G$ such that $v_{0}\sim v_{i_{1}}$ , $v_{0}\sim v_{i_{4}}$ , and $v_{i_{j}}\sim v_{i_{j+1}}$ for $j=1,2,3$ . By similar arguments to the proof of Lemma 2.3, we must have, without loss of generality, $v_{i_{2}}\in V_{0}\setminus\{v_{0},v_{qk}\}$ and $v_{i_{3}}\in V_{1}\setminus\{v_{1}\}$ . Further, since $N(v_{0})=\{v_{1},v_{qk}\}\cup V_{2}\cup V_{3}\cup\cdots\cup V_{k-1}$ , we must have $\{v_{i_{4}},v_{i_{5}}\}\subseteq V_{2}\cup V_{3}\cup\cdots\cup V_{k-1}$ . By a similar argument to that of Case 1 of the proof of Lemma 2.3 and since $v_{1}\sim v_{qk}$ , we must have $v_{i_{4}}\in V_{k-1}$ (or else $v_{i_{2}}\sim v_{i_{4}}$ ) and $v_{i_{3}}\in V_{j}$ for some $2\leq j\leq k-2$ . Further, $j=k-2$ , or else $v_{i_{1}}\sim v_{i_{4}}$ . But now since $k\geq 5$ , and therefore $k-2\geq 3$ , we have $v_{i_{3}}\sim v_{i_{1}}$ . This contradicts our assumption on the induced $C_{5}$ . Therefore, $G$ is $C_{5}$ -free. ∎

Note our proof of the following lemma is adapted directly from Theorem 2.4 of [16] where it was shown that $G(q,4,$ ) (under the name $G_{p}$ ) is $4$ -vertex-critical for all $q$ .

Lemma 2.6.

For all $k\geq 3$ and $q\geq 1$ , $G(q,k)$ is $(k+1)$ -vertex-critical.

Proof.

Let $G=G(q,k)$ . Note that for all $0\leq i\leq(q-1)k+1$ , the set $\{v_{i+j}:j=0,1,\ldots,k-1\}$ induces a $K_{k}$ . Thus, $\chi(G)\geq k$ . Suppose $G$ is $k$ -colourable, and without loss of generality, let vertices $v_{i}$ be assigned colour $i$ for $i=0,1,\ldots,k-1$ . We now must have vertex $v_{j}$ be assigned colour $j\pmod{k}$ for all $k\leq j\leq qk-1$ . But now $N(v_{qk})$ contains all $k$ colours. So $G$ is not $k$ -colourable. From Lemma 2.2, however, this partial colouring is valid and we may give vertex $v_{qk}$ colour $k$ to get that $\chi(G)=k+1$ . Since $v_{qk}$ is the only vertex with colour $k$ , it follows by the symmetry of $G$ that $G$ is $(k+1)$ -vertex-critical. ∎

Theorem 2.7.

There are infinitely many $k$ -vertex-critical $(2P_{2},K_{3}+P_{1},C_{5})$ -free graphs for all $k\geq 6$ .

Proof.

The proof follows from Lemmas 2.3-2.6 ∎

Corollary 2.8.

There are infinitely many $k$ -vertex-critical $(P_{5},C_{5})$ -free graphs for all $k\geq 6$ .

3 State of $(P_{5},H)$ -free graphs when $H$ is of order 5

In this section we detail in a table whether there are only finitely many or infinitely many $k$ -vertex-critical $(P_{5},H)$ -free graphs for all nonisomorphic graphs $H$ of order $5$ . This is to make progress on the open problem raised in [8]. For the names of graphs we are mostly following https://www.graphclasses.org/smallgraphs.html#nodes5 with the notable exception that we use $+$ to denote disjoint union.

Table 1: The state-of-the-art for

H

of order

5

Graph	Graph name	Finite/Infinite	Reference
	$\overline{K_{5}}$	finite	Ramsey’s Theorem [27]
	$P_{2}+3P_{1}$	finite	[7]
	$P_{3}+2P_{1}$	finite	[1]
	claw $+P_{1}$	unknown	N/A
	$K_{1,4}$	finite	[22] (see also [25, Theorem 1])
	$2K_{2}+P_{1}$	infinite	Contains $2K_{2}$ [16]
	$P_{4}+P_{1}$	unknown	N/A
	$P_{3}+P_{2}$	infinite	Contains $2K_{2}$ [16]
	$K_{3}+2P_{1}$	infinite	Contains $K_{3}+P_{1}$ [8, 16]
	chair	finite $k\leq 5$ , unknown $k\geq 6$	[20]
	co-dart	infinite	Contains $K_{3}+P_{1}$ [8, 16]
	$\overline{\text{diamond}+P_{1}}$	unknown	N/A
	$C_{4}+P_{1}$	unknown	N/A
	banner	finite	[3, Theorem 3(i)]
	diamond $+P_{1}$	infinite	Contains $K_{3}+P_{1}$ [8, 16]
	bull	finite $k=5$ , unknown $k\geq 6$	[19]
	dart	unknown	N/A
	$K_{2,3}$	finite	[22]
	$\overline{K_{3}+2P_{2}}$	unknown	N/A
	$P_{5}$	infinite	Contains $2K_{2}$ [16]
	$K_{3}+P_{2}$	infinite	Contains $2K_{2}$ [16]
	co-banner	infinite	Contains $2K_{2}$ [16] (see also [3])
	butterfly	infinite	Contains $2K_{2}$ [16]
	$C_{5}$	finite $k\leq 5$ , infinite $k\geq 6$	[16], Corollary 2.8
	$\overline{P_{5}}$	finite	[14]
	gem	finite	[4] (see also [6])
	kite	infinite	Contains $K_{3}+P_{1}$ [8, 16]
	$K_{4}+P_{1}$	infinite	Contains $K_{3}+P_{1}$ [8, 16]
	$\overline{\text{claw}+K_{1}}$	infinite	Contains $K_{3}+P_{1}$ [8, 16]
	$\overline{P_{3}+2P_{1}}$	unknown	N/A
	paraglider or $\overline{P_{3}+P_{2}}$	finite	[4]
	$W_{4}$	unknown	N/A
	$K_{5}-e$	unknown	N/A
	$K_{5}$	infinite $k=5$ , unknown $k\geq 6$	[16]

References

[1] T. Abuadas, B. Cameron, C. T. Hoàng, and J. Sawada. Vertex-critical $(P_{3}+\ell P_{1})$ -free and vertex-critical (gem, co-gem)-free graphs. preprint, arXiv : 2206.03422[math.CO], 2022.
[2] F. Bonomo, M. Chudnovsky, P. Maceli, O. Schaudt, M. Steinz, and M. Zhong. Three-coloring and list three-coloring of graphs without induced paths on seven vertices. Combinatorica, 38(4):779–801, 2018.
[3] C. Brause, M. Geißer, and I. Schiermeyer. Homogeneous sets, clique-separators, critical graphs, and optimal $\chi$ -binding functions. Discrete Appl. Math., 320:211–222, 2022.
[4] Q. Cai, J. Goedgebeur, and S. Huang. Some results on $k$ -critical $P_{5}$ -free graphs. Discrete Appl. Math., 334:91–100, 2023.
[5] Q. Cai, S. Huang, T. Li, and Y. Shi. Vertex-critical $(P_{5},banner)$ -free graphs. In Frontiers in Algorithmics - 13th International Workshop, FAW 2019, Sanya, China, April 29 - May 3, 2019, Proceedings, volume 11458, pages 111–120, Sanya, China, 2019. Springer.
[6] B. Cameron and C. T. Hoàng. A refinement on the structure of vertex-critical ( $P_{5}$ , gem)-free graphs. Theoretical Computer Science, 961:113936, 2023.
[7] B. Cameron, C. T. Hoàng, and J. Sawada. Dichotomizing $k$ -vertex-critical $H$ -free graphs for $H$ of order four. Discrete Appl. Math., 312:106–115, 2022. Ninth Workshop on Graph Classes, Optimization, and Width Parameters.
[8] K. Cameron, J. Goedgebeur, S. Huang, and Y. Shi. $k$ -critical graphs in $P_{5}$ -free graphs. Theoretical Computer Science, 864:80–91, 2021.
[9] M. Chudnovsky, J. Goedgebeur, O. Schaudt, and M. Zhong. Obstructions for three-coloring graphs without induced paths on six vertices. J. Combin., Ser. B, 140:45–83, 2020.
[10] M. Chudnovsky, N. Robertson, P. Seymour, and R. Thomas. The strong perfect graph theorem. Ann. of Math., 164(1):51–229, 2006.
[11] M. Chudnovsky, S. Spirkl, and M. Zhong. Four-coloring $P_{6}$ -free graphs. I. Extending an excellent precoloring. preprint, arXiv : 1802.02282[math.CO], 2018.
[12] M. Chudnovsky, S. Spirkl, and M. Zhong. Four-coloring $P_{6}$ -free graphs. II. Finding an excellent precoloring. preprint, arXiv : 1802.02283[math.CO], 2018.
[13] M. Chudnovsky, S. Spirkl, and M. Zhong. Four-coloring $P_{6}$ -free graphs. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’19, page 1239–1256, USA, 2019. Society for Industrial and Applied Mathematics.
[14] H. S. Dhaliwal, A. M. Hamel, C. T. Hoàng, F. Maffray, T. J. D. McConnell, and S. A. Panait. On color-critical $(P_{5},$ co- $P_{5})$ -free graphs. Discrete Appl. Math., 216:142–148, 2017.
[15] C. T. Hoàng, M. Kamiński, V. Lozin, J. Sawada, and X. Shu. Deciding $k$ -colorability of $P_{5}$ -free graphs in polynomial time. Algorithmica, 57:74–81, 2010.
[16] C. T. Hoàng, B. Moore, D. Recoskie, J. Sawada, and M. Vatshelle. Constructions of $k$ -critical $P_{5}$ -free graphs. Discrete Appl. Math., 182:91–98, 2015.
[17] I. Holyer. The NP-completeness of edge-coloring. SIAM J. Comput., 10(4):718–720, 1981.
[18] S. Huang. Improved complexity results on $k$ -coloring $P_{t}$ -free graphs. European J. Combin., 51:336–346, 2016.
[19] S. Huang, J. Li, and W. Xia. Critical ( $P_{5}$ , bull)-free graphs. Discrete Applied Mathematics, 334:15–25, 2023.
[20] S. Huang and Z. Li. Vertex-Critical $(P_{5},chair)$ -free Graphs. preprint, arXiv : arXiv:2301.02436 [math.CO], 2023.
[21] M. Kamiński and V. Lozin. Coloring edges and vertices of graphs without short or long cycles. Contrib. Discrete Math., 2(1):61–66, 2007.
[22] M. Kamiński and A. Pstrucha. Certifying coloring algorithms for graphs without long induced paths. Discrete Appl. Math., 261:258–267, 2019.
[23] R. M. Karp. Reducibility among combinatorial problems. In Complexity of computer computations (Proc. Sympos., IBM Thomas J. Watson Res. Center, Yorktown Heights, N.Y., 1972), pages 85–103, 1972.
[24] D. Leven and Z. Gail. NP completeness of finding the chromatic index of regular graphs. J. Algorithms, 4:35–44, 1983.
[25] V. Lozin and D. Rautenbach. Some results on graphs without long induced paths. Inform. Process. Lett., 88(4):167–171, 2003.
[26] F. Maffray and G. Morel. On $3$ -colorable $P_{5}$ -free graphs. SIAM J. Discrete Math., 26(4):1682–1708, 2012.
[27] F. P. Ramsey. On a problem of formal logic. Proc. Lond. Math. Soc., (s2-30):264–286, 1928.

Infinite families of kk-vertex-critical (P5P_{5}, C5C_{5})-free graphs

Abstract

1 Introduction

1.1 Notation and Definitions

2 New infinite families of kk-vertex-critical graphs

Definition 2.1.

Lemma 2.2.

Proof.

Lemma 2.3.

Proof.

Lemma 2.4.

Proof.

Lemma 2.5.

Proof.

Lemma 2.6.

Proof.

Theorem 2.7.

Proof.

Corollary 2.8.

3 State of (P5,H)(P_{5},H)-free graphs when HH is of order 5

References

Infinite families of $k$ -vertex-critical ( $P_{5}$ , $C_{5}$ )-free graphs

2 New infinite families of $k$ -vertex-critical graphs

3 State of $(P_{5},H)$ -free graphs when $H$ is of order 5