A Note Related to Graph Theory

Jinfeng Li

Abstract

This article foucuses on $(P_{3}\cup P_{2},K_{4})$ -free graph. In this paper, we prove that if G is $(P_{3}\cup P_{2},K_{4})$ -free, then $\chi(G)\leq 7$ . We then use this result to obtain the upper bound of order and chromatic number of $(4K_{1},\overline{P_{3}\cup P_{2}},K_{\omega})$ -free graph .

Keywords: coloring; chromatic number; clique number; $\chi$ -binding function; $P_{3}\cup P_{2}$ -free; $K_{4}$ -free.

1 Introduction

A graph $G$ consists of its vertex set $V(G)$ and edge set $E(G)\subseteq V(G)\times V(G)$ . The order of $G$ , denoted by $n$ , is the size of $V(G)$ . The complement of a graph $G$ , denoted by $\overline{G}$ or $co-G$ , is a graph with the same vertex set while whose edge set consists of the edges not present in $E(G)$ .

All graphs in this paper are finite and have no loops or parallel edges. A graph $G$ contains $H$ if $H$ is isomorphic to an induced subgraph of $G$ . If $H_{1}$ is isomorphic to $H_{2}$ , then we say $H_{1}\simeq H_{2}$ . For a collection of graphs $H_{t},t=1,2,...,n$ , $G$ is $(H_{1},H_{2},...,H_{n})$ -free if it does not contain $H_{t},t=1,2,...,n$ . In this paper, if $G$ does not contain $P_{2}$ , we will say that $G$ is edge-free.

Path and cycle on $n$ vertex is denoted by $P_{n}$ and $C_{n}$ , respectively. The complete graph on that has $n$ vertex is denoted bu $K_{n}$ . We use $G\cup H$ to denote the disjoint union of $G$ and $H$ .

A $k$ -coloring of a graph $G$ is a function $\phi:V(G)\rightarrow\{1,...,k\}$ such that $\phi(u)\neq\phi(v)$ whenever $u$ and $v$ are adjacent in $G$ . We say that $G$ is $k$ -colorable if $G$ admits a $k$ -coloring. The chromatic number of $G$ is denoted by $\chi(G)$ which represents the minimum positive integer $k$ such that $G$ is $k$ -colorable. The clique number is denoted by $\omega(G)$ which represents the size of the largest clique in $G$ .

A family $\mathbb{G}$ of graphs is said to be $\chi$ -bounded if there exists a function f such that for every graph $G\in\mathbb{G}$ and every induced subgraph $H$ of $G$ it holds that $\chi(H)\leq f(\omega(H))$ . The function $f$ is called a $\chi$ -binding function for $G$ . The class of perfect graphs (a graph $G$ is perfect if for every induced subgraph $H$ of $G$ it holds that $\chi(H)=\omega(H))$ , for instance, is a $\chi$ -bounded family with $\chi$ -binding function $f(x)=x$ . Therefore, $\chi$ -boundedness is a generalization of perfection. The notion of $\chi$ -bounded families was introduced by Gyárfás who make the following conjecture.

conjecture 1.1.

[3] For every forest T, the class of $T$ -free graphs is $\chi$ -bounded.

For $\omega=3$ , Esperet, Lemoine, Maffray and Morel[2] obtained the optimal bound on the chromatic number: every $(P_{5},K_{4})$ -free graph is 5-colorable. Serge Gaspers and Shenwei Huang[6] obtained the optimal bound of the chromatic number: every $(2P_{2},K_{4})$ -free graph is 4-colorable. Karthick and S. Mishra obtained the optimal bound of the chromatic number: every $(P_{6},diamond,K_{4})$ -free graph is 6-colorable. Rui Li,Jinfeng Li and Di Wu claimed that [5] $(P_{3}\cup P_{2},K_{4})$ -free graph is $9$ -colorable. We follow the methods in this paper and sharper the bound to $7$ .

Partition $V(G)$ into two following parts:

•

$D_{1}:=\{x\in V(G)|\omega(G-N(x))\leq 2\}$
•

$D_{2}:=G-D_{1}$

Let $C=u_{1}v_{1}v_{2}v_{3}u_{3}u_{2}$ be a $6$ -hole. We use $co-donino$ to denote a graph obtained from $C$ by connecting edges $v1v3$ and $u1u3$ .

Let $C=u_{1}v_{1}v_{2}v_{3}u_{3}u_{2}$ be a $6$ -hole. We use $co-A$ to denote a graph obtained from $C$ by connecting edges $v_{1}v_{3}$ , $u_{1}u_{3}$ and $u_{1}v_{3}$ .

Our proof includes three major theorem:

theorem 1.1.

If $G[D_{1}]$ contains $P_{2}\cup P_{1}$ , then $\chi(G)\leq 7$ .

theorem 1.2.

If $G$ contains $co-domino$ or $co-A$ , then $\chi(G)\leq 7$ .

theorem 1.3.

If $G$ is $(co-domino,co-A)$ -free and $G[D_{2}]$ is not an induced subgraph of $K_{3}$ , then $\chi(G)\leq 7$ .

Finally, we obtain a theorem for $(4K_{1},\overline{P_{3}\cup P_{2}})$ -free graphs:

theorem 1.4.

If $G$ is $(4K_{1},\overline{P_{3}\cup P_{2}})$ -free with clique number $\omega$ and order n, then $n\leq 7\omega$ and $\chi(G)\leq 4\omega$ .

2 Structure Around $K_{3}$

Suppose there is a $K_{3}$ in $G$ and its vertex set is $\{v_{1},v_{2},v_{3}\}$ . Naturally, we can divide $V(G)$ into following three sets:

•

$A_{0}:=\{v|v\text{ is not adjacent to any vertex in }\{v_{1},v_{2},v_{3}\}\}$ .
•

$A_{1}:=\{v|v\text{ is adjacent to one vertex in }\{v_{1},v_{2},v_{3}\}\text{ only}\}$ .
•

$A_{2}:=\{v|v\text{ is adjacent to two vertex in }\{v_{1},v_{2},v_{3}\}\text{ only}\}$ .

we need to combine $A_{0}$ and $A_{1}$ and divide it into three disjoint sets: $B_{1},B_{2},B_{3}$ . The set $B_{1}$ includes vertices that is only adjacent to $u_{1}$ and vertices in $A_{0}$ . The set $B_{j},j=2,3$ includes vertices that are only adjacent to $u_{j}$ . Since $G[B_{i}]$ is anticomplete to an edge in $G[\{v_{1},v_{2},v_{3}\}]$ , $G[B_{i}],i=1,2,3$ is $P_{3}$ -free.

$A_{2}\cup\{v_{1},v_{2},v_{3}\}$ can be partitioned in to $(N(v_{i})\cap N(_{i-1}))\cup\{v_{i+1}\}$ (mod3) for $i=1,2,3$ . It is easy to obtain that $\chi((N(v_{i})\cap N(_{i-1}))\cup\{v_{i+1}\})\leq 1$ (mod3) for $i=1,2,3$ .

3 main theorem

We first introduce a lemma provided by Rui Li, Jinfeng Li and Di Wu.

lemma 3.1.

[5] If $G$ contains $P_{2}\cup K_{3}$ , then $\chi(G)\leq 6$ .

Define $D_{1}:=\{x|\omega(G-N(x))\leq 2\}$ and $D_{2}:=G-D_{1}$ .

claim 3.2.

For any two nonadjacent vertex $y_{1},y_{2}$ in $D_{1}$ , $\omega(G[N(y_{1})-N(y_{2})])\leq 1$ and $\omega(G[N(y_{2})-N(y_{1})])\leq 1$ .

Proof. If there is an edge in $G[N(y_{1})-N(y_{2})]$ (or $G[N(y_{2})-N(y_{1})]$ ), then $\omega(G[N(y_{1})-N(y_{2})])=3$ (or $\omega(G[N(y_{2})-N(y_{1})])=3$ ), which contradicts definition of $y_{1}$ (or $y_{2}$ ).∎

We fisrt introduce a lemma to help us slightly determine the structure of $G[D_{1}]$ .

theorem.

(1.1) If $G[D_{1}]$ contains $P_{2}\cup P_{1}$ , then $\chi(G)\leq 7$ .

Proof. Suppose $G[\{v_{1},v_{2}\}\cup\{v_{3}\}]\simeq P_{2}\cup P_{1}$ , $M(v_{1},v_{2})=G-\{v_{1},v_{2}\}-(N(v_{1})\cup N(v_{2}))$ . we can divide $G$ into $\{v_{1},v_{2}\}\cup(N(v_{1})\cup N(v_{2}))\cup M(v_{1},v_{2})$ . Since $G$ is $(P_{3}\cup P_{2},P_{2}\cup K_{3})$ -free, $G[M(v_{1},v_{2})]$ is unions of clique and $\omega(M(v_{1},v_{2}))\leq 2$ . Therefore, $\{v_{1},v_{2}\}\cup M(v_{1},v_{2})\leq 2$ .

We will prove $\chi(N(v_{1})\cup N(v_{2}))\leq 5$ and hence $\chi(G)\leq 7$ . $N(v_{1})\cup N(v_{2})$ can be divided into $N(v_{1})-N(v_{3})$ , $(N(v_{1})\cap N(v_{3}))-N(v_{2})$ , $N(v_{2})-N(v_{3})$ , $(N(v_{2})\cap N(v_{3}))-N(v_{1})$ and $N(v_{1})\cap N(v_{2})$ . We apply claim 3.3 to prove that the clique number of first four sets are at most 1. If the last set has edge, then $\omega(G)\geq 4$ . Therefore, $\chi(N(v_{1})\cup N(v_{2}))\leq 5$ . ∎

observation 1.

If $G[D_{1}]$ is $P_{2}\cup P_{1}$ -free, then $\overline{G[D_{1}]}$ is $P_{3}$ -free.

Now we introduce a lemma which is important in the proof of theorem1.2.

claim 3.3.

Suppose $V(G)$ can be partitioned into three nonempty subsets $V_{1}$ , $V_{2}$ and $V_{3}$ such that $G[V_{1}]$ and $G[V_{2}]$ are $(K_{3},P_{3})$ -free graph, $G[V_{3}]$ is a stable set , $G[V_{1}\cup V_{2}]$ is $K_{3}$ -free , $G[V_{j}\cup V_{3}]$ is $(K_{3},P_{3})$ -free graph for $j=1,2$ and any vertex $v$ in $V_{i},i=1,2$ , $M(v)-V_{i}$ has no edge. Furthermore, for any vertex $v\in V_{3}$ , if $N(v)\cap V_{i}\neq\emptyset$ , then $N(v)\cap V_{i}=\{x\in V_{i}|x\text{ is not complete to }N(v)\cap N_{3-i}\},i=1,2$ . If $G[V_{1}]$ has at most one edge, then $\chi(G)\leq 3$ .

Proof.

If $V_{1}$ has no edge, then randomly select one vertex $v\in V_{1}$ . We partition $V(G)$ accoding to $\{v\}$ , that is $V(G)=\{v\}\cup N(v)\cup M(v)$ . $|N(v)\cap V_{3}|\leq 1$ . Now we partition $V(G)$ into three stable set: $(N(v)\cap V_{3})\cup(V_{1}\cap M(v))$ , $N(v)\cap V_{2}$ and ${v}\cup(M(v)-V_{1})$ . $(N(v)\cap V_{3})\cup(V_{1}\cap M(v))$ is stable set as $G[V_{3}\cup V_{1}]$ is $P_{3}$ -free. According to definition, the rest two sets are stable sets.

If $V_{1}$ has one edge, then set one vertex of the vertex set of that edge $v$ . We partition $V(G)$ into three part: $V(G)=\{v\}\cup N(v)\cup M(v)$ . It is obvious that $N(v)\subseteq V_{2}$ , otherwise $G[V_{1}\cup V_{2}]$ induces an $P_{3}\cup P_{2}$ or $K_{3}\cup P_{2}$ . Therefore, as $G[V_{1}\cup V_{2}]$ is $K_{3}$ -free, we can conclude that $\chi(N(v))\leq 1$ . $\chi(M(v))\leq\chi(M(v)\cap V_{1})+\chi(M(v)-V_{1})\leq 2$ and hence $\chi(G)\leq\chi(N(v))+\chi(\{v\}\cup M(v))\leq 3$ . ∎

observation 2.

If $G$ contains $co-domino$ , then according to section 2.1, $V(G)$ can be partitioned into $B_{1},B_{2},B_{3}$ and $A_{2}$ .

lemma 3.4.

If $G$ contains $co-domino$ , then $\chi(G)\leq 7$ .

Proof.

$\omega(G[B_{2}])\leq 1$ . Otherwise there exists an edge in $G[B_{2}]$ . We call the edge $G[\{y_{1},y_{2}\}]$ . If $y_{1}\sim u_{2}$ , then $G[\{v_{1},v_{3}\}\cup\{y_{2},y_{1},u_{2}\}]\simeq P_{3}\cup P_{2}$ or $G[\{v_{1},v_{3}\}\cup\{y_{2},y_{1},u_{2}\}]\simeq K_{3}\cup P_{2}$ (depending on whether $y_{2}$ is adjacent to $u_{2}$ ). As a consequence, both $y_{1}$ and $y_{2}$ are not adjacent to $u_{2}$ . However, $y_{1}$ is complete to $\{u_{1},u_{3}\}$ , which can be proven through making use of $P_{2}\cup P_{3}$ -free. Similarly, $y_{2}$ is complete to $\{u_{1},u_{3}\}$ . As a consequence, $G[\{y_{1},y_{2},u_{3},u_{1}\}]\simeq K_{4}$ , which contradicts the fact that $\omega(G)\leq 3$ . As a consequence, $\chi(B_{2})\leq 1$ .

For any $x\in B_{2}$ , $N(x)$ must be one of four following sets: $\{u_{1},u_{2}\}$ , $\{u_{2},u_{3}\}$ , $\{u_{2}\}$ and $\{u_{3},u_{1}\}$ . We partition $B_{2}$ ( $\{u_{1},u_{2}\}$ ) into $C_{1}$ ( $\{u_{2},u_{3}\}$ ), $C_{2}$ ( $\{u_{2},u_{3}\}$ ), $C_{3}$ ( $\{u_{2}\}$ ) and $C_{4}$ ( $\{u_{3},u_{1}\}$ ) accoding to their neigbors in $\{u_{1},u_{2},u_{3}\}$ . Trivially , $C_{i}\cap C_{j}=$ for $i\neq j\in\{1,2,3,4\}$ .

If $C_{1}\neq\emptyset$ , then there is no edge in $G[B_{3}]$ . Suppose $\{y_{1},y_{2}\}\in E(B_{3})$ and $x\in C_{1}$ , we are going to prove $y_{i},i=1,2$ are complete to $\{v_{1},x\}$ and anticomplete to $\{u_{2},u_{3}\}$ and hence $G[\{y_{1},y_{2},u_{1},x\}]\simeq K_{4}$ , which contradicts $\omega(G)\textless 4$ . If $y_{1}$ is adjacent to $u_{2}$ , then $G[\{y_{1},u_{3},u_{2}\}\cup\{v_{2},v_{1}\}]$ is isomorphic to $P_{2}\cup P_{3}$ or $P_{2}\cup K_{3}$ . Symmetrically, $y_{2}$ is anticomplete to $\{u_{2},u_{3}\}$ . As consequence, $y_{1}$ must be complete to $\{u_{1},x\}$ , or $G[\{u_{2},u_{1},x,v_{2},v_{3},y_{1}\}]$ will induce $P_{3}\cup P_{2}$ . Symmetrically, $y_{2}$ is complete to $\{x,u_{1}\}$ . As consequence, we get the contradiction that $G[\{y_{1},y_{2},u_{1},x\}]\simeq K_{4}$ . Therefore, $\omega(B_{3})\leq 1$ .

If $C_{2}\neq\emptyset$ , then there is no edge in $G[B_{1}-A_{0}]$ , which is similar to the proof for $C_{1}\neq\emptyset.$

From dicussion above, if $C_{1}\cup C_{2}\neq\emptyset$ , then $\chi(B_{1}\cup B_{2}\cup B_{3})\leq 4$ and hence $\chi(G)\leq\chi(B_{1}\cup B_{2}\cup B_{3})+\chi(A_{2}\cup\{v_{1},v_{2},v_{3}\})\leq 4+3=7$ .

Suppose $C_{1}\cup C_{2}=\emptyset$ and $x\in C_{3}$ . Furthermore, $|C_{3}|\leq 1$ . Otherwise, $G[\{u_{2}\}\cup\{v_{1},v_{3}\}\cup C_{3}]$ induces $P_{3}\cup P_{2}$ or $P_{2}\cup K_{3}$ . According to the definition, $A_{2}$ can be partitioned into $N(v_{1})\cap N(v_{2})$ , $N(v_{1})\cap N(v_{3})$ and $N(v_{2})\cap N(v_{3})$ .

Suppose there is a vertex in $(N(v_{2})\cap N(v_{3})$ has only one neighbor in $\{u_{1},u_{2},u_{3}\}$ . It is not difficult to obtain that the only neighbor is $v_{2}$ . If we exchange $\{v_{1},v_{2},v_{3}\}$ and $\{u_{1},u_{2},u_{3}\}$ in $co-domino$ , then we can prove $\chi(G)\leq 7$ in the same way as what we did when $C_{1}\cup C_{2}\neq\emptyset$ .

Suppose evrey vertex in $A_{2}\cap N(v_{2})$ has two neighbors in $\{u_{1},u_{2},u_{3}\}$ .

Let $C=u_{1}v_{1}v_{2}v_{3}u_{3}u_{2}$ be a $co-domino$ and $\{u,x\}$ be two vertex outside $C$ . We use co-donino1 to denote a family of graphs obtained from $\{u,x\}\cup C$ by connecting edges $uu_{1},uu_{2},uv_{1},uv_{2},xv_{2},xu_{2}$ and $xu$ can be connected or disconnected.

Let $C=u_{1}v_{1}v_{2}v_{3}u_{3}u_{2}$ be a $co-domino$ and $\{u,x\}$ be two vertex outside $C$ . We use co-domino2 to denote a graph obtained from $C$ by connecting edges $uu_{1},uu_{2},uv_{1},uv_{3},xv_{2},xu_{2}$ and $xu$ . Suppose $u\in N(v_{2})\cap N(v_{1})$ . The following case shows that if $u$ is complete to $\{u_{1},u_{2}\}$ or complete to $\{u_{2},u_{3},x\}$ , then $\chi(G)\leq 7$ . In other words, if $G$ contains co-domino1 or co-domino2, then $\chi(G)\leq 7$ .

Recalling that $G[B_{3}]$ is anticomplete to $u_{2}$ , $B_{3}-\{u_{3}\}$ is anticomplete to $u_{2}$ .

case1: $G$ contains $co-domino1$ or $co-domino2$ .

Suppose $G$ contains $co-domino1$ .

$G[B_{3}]$ contains at most one edge. Otherwise, suppose $G[B_{3}]$ contains more than one edge. Since $G[B_{3}]$ is $P_{3}$ -free and complete to $\{u_{1}\}$ and anticomplete to $\{u_{3}\}$ , there exists an $m$ such that these edges are isomorphic to $mK_{2},m\textgreater 1$ and $u$ has at most one neighbor in every edges or $G[\{u,u_{1}\}\cup B_{3}]$ induces $K_{4}$ . However, $m\textgreater 1$ leads to a contradiction that $G[\{B_{3}-N(u)\}\cup\{u,u_{2}\}]$ induces $P_{3}\cup P_{2}$ .

Let $G[B_{1}-A_{0}]=V_{1}^{\prime},G[B_{3}]=V_{2}^{\prime},G[A_{0}]=V_{3}^{\prime}$ . According to claim3.3, $\chi(B_{3}\cup B_{1})\leq 3$ . Therefore, $\chi(G)\leq\chi(B_{1}\cup B_{3})+\chi(B_{2})+\chi(A_{2})\leq 3+1+3=7$ .

Suppose $G$ is $co-domino1$ -free and contains $co-domino2$ .

$G[B_{1}-A_{0}]$ contains at most one edge. Since $G[B_{1}-A_{0}]$ is $P_{3}$ -free and complete to $\{u_{1}\}$ and anticomplete to $\{u_{3}\}$ , this union of edges is isomorphic to $mK_{2},m\textgreater 1$ for some $m$ and $u$ has at most one neighbor in every edge or $G[\{u,x\}\cup B_{3}]$ induces $K_{4}$ . However, $m\textgreater 1$ leads to a contradiction that $G[\{B_{3}-N(u)\}\cup\{u,u_{2}\}]$ induces $P_{3}\cup P_{2}$ .

Let $G[B_{1}-A_{0}]=V_{1}^{\prime},G[B_{3}]=V_{2}^{\prime},G[A_{0}]=V_{3}^{\prime}$ , then according to claim3.3, $\chi(B_{3}\cup B_{1})\leq 3$ . Furthermore, $\chi(G)\leq\chi(B_{1}\cup B_{3})+\chi(B_{2})+\chi(A_{2})\leq 3+1+3=7$ . Let Let $C=u_{1}v_{1}v_{2}v_{3}u_{3}u_{2}$ be a $co-domino$ and $\{u,x\}$ be two vertex outside $C$ . We use co-domino3 to denote a graph obtained from $C$ by connecting edges $uu_{1},uu_{2},uv_{1},uv_{3},xv_{2}$ and $xu_{2}$ .

Suppose $u\in N(v_{1})\cap N(v_{2})$ and $u\sim u_{2},u\sim u_{3},u\not\sim x$ . The following case shows that if $u$ exists, then $\chi(G)\leq 7$ . In other words, if $G$ contains $co-domino3$ , then $\chi(G)\leq 7$ .

Partition $A_{2}=(N(v_{1})\cap N(v_{2}))\cup(N(v_{2})\cap N(v_{3}))\cup(N(v_{1})\cup N(v_{3}))$ into following five vertex sets.

$D_{1}:=N(v_{1})\cap N(v_{2})\cap N(u_{2})\cap N(u_{3})$ .
$D_{2}:=N(v_{1})\cap N(v_{2})\cap N(u_{1})\cap N(u_{3})$ .
$D_{3}:=N(v_{2})\cap N(v_{3})\cap N(u_{1})\cap N(u_{2})$ .
$D_{4}:=N(v_{2})\cap N(v_{3})\cap N(u_{1})\cap N(u_{3}).$
$D_{5}:=N(v_{1})\cap N(v_{3}).$

case2: Suppose $G$ contains $co-domino3$ .

Suppose $\{u,u^{\prime}\}\subseteq E[D_{1},D_{3}]$ .

$\chi(B_{1}\cup B_{3}-\{u_{1},u_{3}\})\leq 3$ . Define $I:=B_{1}\cup B_{3}-\{u_{1},u_{2},u_{3}\}$ . Recalling that $B_{1}\cup B_{3}-A_{0}$ is anticomplete to $\{u_{2}\}$ and that $A_{0}$ is anticomplete to $\{v_{1},v_{2},v_{3}\}$ , $I$ is anticomplete to $\{v_{2},u_{2}\}$ . Therefore, $I-N(u)$ is anticomplete to $\{v_{2},u,u_{2}\}$ . Since $G[\{v_{2},u,u_{2}\}]\simeq P_{3}$ , $I-N(u)$ is a stable set and hence $\chi(I-N(u))\leq 1$ . Similarly, $\chi((I\cap N(u))-N(u^{\prime}))\leq 1$ . Trivially, $(I\cap N(u)\cap N(u^{\prime}))\cup\{u_{2}\}$ is stable set and hence the chromatic number is less than 2. Therefore, $\chi(G)\leq\chi(I-N(u))+\chi((I\cap N(u))-N(u^{\prime}))+\chi((I\cap N(u)\cap N(u^{\prime}))\cup\{u_{2}\})\leq 1+1+1=3.$

$G[D_{1}\cup\{u_{1}\}\cup\{x\}\cup\{v_{3}\}]$ is a stable set. If $E[\{x\},D_{1}]\neq\emptyset$ , then $G$ contains $co-domino2$ . Accoding to definition, $E[\{u_{1}\},D_{1}\cup\{x\}]=\emptyset$ . The rest is obvious.

$G[D_{2}\cup D_{4}\cup(B_{2}-\{x\})]$ is a stable set. Recalling that $|C_{3}|\leq 1$ and $C_{1}=C_{2}=\emptyset$ , $B_{2}-\{x\}=C_{4}$ . According to definition $D_{2}\cup D_{4}\cup(B_{2}-\{x\})$ is complete to $\{u_{1},u_{3}\}$ and the rest is obvious.

$G[D_{3}\cup\{u_{3}\}\cup\{v_{1}\}]$ is a stable set. According to definition, $E[D_{3},u_{3}]=\emptyset$ and $G[E_{3}]$ is a stable set. The rest is obvious.

Let $D_{5}^{\prime}$ be $D_{5}\cup\{v_{2}\}$ . $\chi(G)\leq\chi(B_{1}\cup B_{3}-\{u_{1},u_{3}\})+\chi(D_{1}\cup\{u_{1}\}\cup\{x\}\cup\{v_{3}\})+\chi(D_{2}\cup D_{4}\cup(B_{2}-\{x\}))+\chi(D_{3}\cup\{u_{3}\}\cup\{v_{1}\})\leq 4+1+1+1=7.$

Suppose $E[D_{1},D_{3}]=\emptyset$ .

$G[D_{1}\cup D_{3}\cup\{x\}]$ is a stable set. If $E[\{x\},D_{1}\cup D_{3}]\neq\emptyset$ , then $G$ contains $co-domino2$ . Since $E[D_{1},D_{3}]=\emptyset$ , $G[D_{1}\cup D_{3}\cup\{x\}]$ .

$\chi(G)\leq\chi(D_{1}\cup D_{3}\cup\{x\})+\chi(D_{2}\cup D_{4}\cup(B_{2}-\{x\}))+\chi(B_{1}\cup\{v_{2},v_{3}\})+\chi(B_{3}\cup\{v_{1}\})+\chi(D_{5})\leq 1+1+2+2+1\leq 7$ .

Combining $co-domino2$ -free, $do-domino3$ -free and our supposition that evrey vertex in $A_{2}\cap N(v_{2})$ has two neighbors in $\{u_{1},u_{2},u_{3}\}$ , if $u\in N(v_{1})\cap N(v_{2})$ , then $u$ is complete to $\{u_{1},u_{3}\}$ . Similarly, if $u\in N(v_{2})\cap N(v_{3})$ ,then $u$ is complete to $\{u_{1},u_{3}\}$ . Therefore, $G[(N(v_{1})\cap N(v_{2}))\cup(N(v_{2})\cap N(v_{3}))]$ is a stable set.

Furthermore, $\chi(N(v_{2})-\{v_{1},v_{3}\})\leq 2$ . Noticing that $N(v_{2})=(N(v_{1})\cap N(v_{2}))\cup(N(v_{3})\cap N(v_{2}))\cup C_{3}\cup C_{4}$ , the proof is easy.

$\chi(G)\leq\chi(N(v_{2})-\{v_{1},v_{3}\})+\chi(B_{1}\cup\{v_{2},v_{3}\})+\chi(B_{3}\cup\{v_{1}\})+\chi(N(v_{1})\cap N(v_{3}))\leq 2+2+2+1=7.$

Therefore, if $C_{3}\neq\emptyset$ , $\chi(G)\leq 7.$

Suppose $C_{1}=C_{2}=C_{3}=\emptyset$ . We continue to use notations $D_{1},D_{2},...,D_{5}$ . Similar to case2, $\chi(G)\leq 7$ .(The proof does not depend on the existence on {x}.)∎

Let $C=v_{1}v_{2}v_{3}u_{3}u_{2}u_{1}$ be a $6$ -hole and $\{u\}$ be a vertex outside the $6$ -hole. We use $X_{1}$ to denote a graph obtained from $\{u\}\cup C$ by connecting edges $v_{1}v_{3},uv_{1}$ and $uu_{2}$ .

Let $C=v_{1}v_{2}v_{3}u_{3}u_{2}u_{1}$ be a $6$ -hole and $\{u\}$ be a vertex outside the $6$ -hole. We use $X_{2}$ to denote a graph obtained from $\{u\}\cup C$ by connecting edges $v_{1}v_{3},v_{3}u_{1}$ , $u_{1}u_{3},v_{2}u$ and $uu_{2}$ .

The following figures are $X_{1}$ and $X_{2}$ ( from left to right).

lemma 3.5.

Suppose $G$ is $co-domino$ -free and contains $X_{1}$ or $X_{2}$ , then $\chi(G)\leq 7$ .

Proof.

case1:G contains $X_{1}$ .

$G[B_{1}-A_{0}-\{u_{1}\}]$ is anticomplete to $\{u_{1},u_{2}\}$ and complete to $\{u,u_{3}\}$ .Suppose $y\in B_{1}-A_{0}$ and $y\sim u_{1}$ (or $u_{2}$ ) only, then $G[\{y,u_{1},u_{2}\}\cup\{v_{3},v_{1}\}]\simeq P_{3}\cup P_{2}$ . Therefore, $y$ must complete to both $u_{2}$ and $u_{1}$ and hence we get $G[\{y,u_{1},u_{2}\}\cup\{v_{1},v_{3}\}]\simeq K_{3}\cup P_{2}$ ,which contradics our assumption. $G[B_{2}]$ is complete to $\{u_{3}\}$ (or $u$ ) or $G[(B_{2}-A_{0})\cup\{v_{1},v_{2}\}\cup\{u_{3},u_{2}\}]$ will induce an $P_{3}\cup P_{2}$ ( $G[(B_{2}-A_{0})\cup\{v_{1},v_{2}\}\cup\{u,u_{2}\}]$ will induce a $P_{3}\cup P_{2}$ ).

Symmetrically , $G[B_{3}-\{u_{3}\}]$ is anticomplete to $\{u_{2},u_{3}\}$ and complete to $\{u,u_{1}\}$ and $G[B_{2}]-\{u\}$ is anticomplete to $\{u_{1},u_{3}\}$ and anticomplete to $\{u,u_{2}\}$ .

Either $G[B_{1}-A_{0}]$ or $G[B_{3}]$ is edge-free. According to the above paragraph, $G[(B_{1}-A_{0})\cup B_{3}]$ is complete to $u$ and hence it is $K_{3}$ -free. Suppose there is an edge in $G[B_{1}-A_{0}]$ ( $y_{1},y_{2}$ ) and an edge in $G[B_{3}]$ ( $y_{3},y_{4}$ ).

We prove $G[v_{4},y_{1},y_{2},y_{3},y_{4},v_{6}]\simeq co-domino$ to obtain a contradicion. It is easy to see that $y_{3}$ should have at least one neighbor in $\{y_{2},y_{1}\}$ . So does $y_{4}$ . Consequently, $G[\{y_{1},y_{2},y_{3},y_{4}\}]\simeq C_{4}$ , otherwise $G[\{x_{1},x_{2},y_{1},y_{2}\}]$ must contain $K_{3}$ .

Symmetrically, either $G[B_{1}-A_{0}]$ or $G[B_{2}]$ is edge-free and either $G[B_{2}]$ or $G[B_{3}]$ is edge-free.

$\chi(B_{1}\cup B_{2}\cup B_{3})\leq 4$ . Recalling that $G[B_{i}]$ is $P_{3}$ -free. Suppose $G[B_{1}-A_{0}]$ has edge, then $\chi(B_{2})\leq 1,\chi(B_{3})\leq 1$ . If $G[B_{2}]$ or $G[B_{3}]$ contains edge, then we can prove $\chi(B_{1}\cup B_{2}\cup B_{3})\leq 4$ . If $G[B_{1}-A_{0}]$ , $G[B_{2}]$ and $G[B_{3}]$ are all edge-free, then it is trvial that $\chi(B_{1}\cup B_{2}\cup B_{3})\leq 4$ .

Therefore, $\chi(G)\leq\chi(B_{1}\cup B_{2}\cup B_{3})+\chi(A_{2})\leq 4+3=7.$

case2: $G$ is $X_{1}$ -free and contains $X_{2}$ .

Accoring to section 2.1, we partition $V(G)$ around $G[\{v_{1},v_{2},v_{3}\}]$ .

Every vertex in $B_{2}-\{u\}$ is adjacent to $u_{3}$ and not adjacent to $u_{2}$ . If there is $x\in B_{2}-\{u\}$ such that $x$ is not adjacent to $u_{3}$ , then $x$ is adjacent to $u_{2}$ . Otherwise $G[\{v_{1},v_{2},x\}\cup\{u_{2},u_{3}\}]\simeq P_{3}\cup P_{2}$ or $K_{3}\cup P_{2}$ . Therefore, we can simply suppose there is $x\in B_{2}-\{u\}$ such that $x$ is adjacent to $u_{2}$ . However, $G[\{u,u_{2},x\}\cup\{v_{1},v_{3}\}]\simeq P_{3}\cup P_{2}$ or $K_{3}\cup P_{2}$ (depending on the adjacency of $u$ and $x$ ). Therefore, such $x$ does not exist.

Every vertex in $B_{1}-A_{0}$ is adjacent to $\{u_{3}\}$ .

Every vertex in $B_{3}$ is anticomplete to $\{u_{2},u_{3}\}$ .

Partition $B_{1}\cup B_{2}\cup B_{3}-A_{0}$ into the folloing six sets.

•

$D_{1}:=\{x\in(B_{2}-\{u\})|x\text{ is adjacent to }u_{1}\text{ and }u_{3}\}$ .
•

$D_{2}:=\{x\in(B_{2}-\{u\})|x\text{ is adjacent to }u_{3}\text{ only}\}$ .
•

$D_{3}:=\{x\in(B_{1}-A_{0})|x\text{ is adjacent to }u_{3}\text{ only}\}$ .
•

$D_{4}:=\{x\in(B_{1}-A_{0})|x\text{ is adjacent to }u_{1}\text{ and }u_{3}\}.$
•

$D_{5}:=\{x\in B_{3}|x\text{ is adjacent to }u_{1}\}.$
•

$D_{6}:=\{x\in B_{3}|x\text{ has no neighbor in }\{u_{1},u_{2},u_{3}\}\}.$

Since $D_{1}\cup D_{4}$ is compete to $\{u_{1},u_{3}\}$ and $u_{1}\sim u_{3}$ , $G[D_{1}\cup D_{4}]$ has no edge and hence $\chi(D_{1}\cup D_{4})\leq 1$ .

Since $D_{2}$ and $D_{3}$ anticomplete to $\{v_{3},u_{1},u_{2}\}$ , $G[D_{2}\cup D_{3}]$ is $P_{2}$ -free and hence $\chi(D_{2}\cup D_{3})\leq 1$ .

$E[\{u\},A_{0}\cup D_{6}]=\emptyset$ . Since $\{u\}\cup D_{6}$ is anticomplete to $\{v_{1},u_{1},u_{3}\}$ and $G[\{v_{1},u_{1},u_{3}\}]\simeq P_{3}$ , $G[\{u\}\cup D_{6}]$ has no edge. Since $\{u\}\cup A_{0}$ is anticomplete $v_{1},v_{3},u_{3}$ and $G[\{v_{1},v_{3},u_{3}\}]\simeq P_{3}$ (It is trivial that $u_{3}$ is anticomplete to $A_{0}$ ), $G[\{u\}\cup A_{0}]$ has no edge.

Since $D_{6}\cup A_{0}$ is anticomplete to $\{v_{2},v_{1},u_{1}\}$ and $G[\{v_{2},v_{1},u_{1}\}]\simeq P_{3}$ , $G[A_{0}\cup D_{6}]$ has no edge and hence $G[\{u\}\cup D_{6}\cup A_{0}]$ has no edge.

$\chi(B_{1}\cup B_{2}\cup B_{3})\leq\chi(D_{1}\cup D_{4})+\chi(D_{2}\cup D_{3})+\chi(A_{0}\cup\{u\}\cup D_{6})+\chi(D_{5})\leq 4$ . Therefore, $\chi(G)\leq\chi(B_{1}\cup B_{2}\cup B_{3})+\chi(A_{2})\leq 7.$ ∎

Suppose all graphs are $(co-domino,K_{3}\cup P_{2},X_{1},X_{2})$ -free.

Let $C=v_{1}v_{2}v_{3}v_{4}v_{5}$ be a $5$ -hole. We use $co-twin-C_{5}$ to denote a graph obtained from $C$ by adding a vertex $\{v_{6}\}$ which is only adjacent $\{v_{3},v_{4},v_{5}\}$ .

Let $C=v_{1}v_{2}v_{3}u_{3}u_{2}u_{1}$ be a $6$ -hole and $\{u\}$ be a vertex outside the $6$ -hole. We use $\mathcal{Y}$ to denote a family of graphs obtained from $\{u\}\cup C$ by connecting edge $uv_{1},uv_{2}$ and $uu_{2}$ and it does not matter whether $uu_{1}$ is connected or not.

Define $M(v_{1},v_{2}):=G-N(v_{1})-N(v_{2})-\{v_{1},v_{2}\}$ . In this lemma, $N(v_{1})$ does not include $\{v_{2}\}$ and $N(v_{2})$ does not include $\{v_{1}\}$ . We introduce a partition which is useful in the following lemma.

observation 3.

If $G$ contains $co-twin-C_{5}$ . $V(G)$ can be partitioned into $\{v_{1},v_{2}\},N(v_{2})\cup N(v_{1})$ and $M(v_{1},v_{2})$ .

lemma 3.6.

If $G$ contains $co-twin-C_{5}$ , then $\chi(G)\leq 7$ .

Proof.

case1: G contains an element of $\mathcal{Y}$ .

$G[B_{1}-A_{0}]$ is complete to $\{u_{3}\}$ and anticomplete to $\{u_{1},u_{2}\}$ . Otherwise, suppose there is $x\in G[B_{1}-A_{0}]$ which is not adjacent to $\{u_{3}\}$ or has neighbor in $\{u_{1},u_{2}\}$ . If $x$ has neighbor in $\{u_{1},u_{2}\}$ , then $G[\{x,u_{1},u_{2}\}\cup\{v_{2},v_{3}\}]$ induces $P_{3}\cup P_{2}$ or $K_{3}\cup P_{2}$ . Therefore, $x$ is not adjacent to $u_{3}$ and hence $G[\{v_{2},x\}]\simeq P_{2}$ is anticomplete to $G[\{u_{1},u_{2},u_{3}\}]\simeq P_{3}$ . Therefore, such $x$ does not exist.

Similarly, $G[B_{3}]$ is complete to $\{u_{1}\}$ and anticomplete to $\{u_{3},u_{2}\}$ .

Either $G[B_{1}-A_{0}]$ or $G[B_{3}]$ has no edge. Otherwise, suppose there is an edge( $y_{1},y_{2}$ ) in $G[B_{1}-A_{0}]$ and an edge( $y_{3},y_{4}$ ) in $G[B_{3}]$ . If $G[\{y_{1},y_{2},y_{3},y_{4}\}]$ induces $diamond$ or $C_{4}$ , then $G[\{u_{1},u_{2},u_{3},y_{1},y_{2},y_{3},y_{4}\}]$ induces $X_{1}$ or $X_{2}$ . Therefore, $G[\{y_{1},y_{2},y_{3},y_{4}\}]$ is not isomorphic to $diamond$ , $C_{4}$ and $K_{4}$ . However, such condition requires $G[\{y_{1},y_{2},y_{3},y_{4}\}]$ to be isomorphic to $P_{4}$ or $2K_{2}$ . Therefore, there must be a vertex has degree one in $G[\{y_{1},y_{2},y_{3},y_{4}\}]$ . Suppose $d(y_{1})=1$ in $G[\{y_{1},y_{2},y_{3},y_{4}\}$ . Then $y_{1}$ is anticomplete to $\{y_{3},y_{4}\}$ and hence $G[\{u_{2},u_{3},y_{1}\}\cup\{y_{3},y_{4}\}]\simeq P_{3}\cup P_{2}$ . Therefore, either $y_{1},y_{2}$ does not exist or $\{y_{3},y_{4}\}$ does not exists.

$G[B_{2}]$ is complete to $\{u_{3}\}$ . Otherwise, suppose there exists $z\in G[B_{2}]$ such that z is not adjacent to $\{u_{3}\}$ . $z$ is adjacent to $u_{2}$ , otherwise $G[\{v_{1},v_{2},z\}\cup\{u_{2},u_{3}\}]\simeq P_{3}\cup P_{2}$ . Since $G[\{x,u_{1},u_{2},u_{3},v_{1},v_{2},v_{3}\}]\simeq X_{1}$ , $z$ is adjacent to $u_{1}$ . However, if $z$ is adjacent to $u_{1}$ , then $G[\{z,u_{1},u_{2},v_{1},v_{2},v_{3}\}]\simeq co-domino$ . Therefore, such $z$ does not exist.

$G[B_{2}]$ contains at most one edge. Suppose there are two edges in $G[B_{3}]$ ( $\{y_{1},y_{2}\}$ and $\{y_{3},y_{4}\}$ ). Because $v_{2}$ is complete to $\{u,y_{1},y_{2},y_{3},y_{4}\}$ . $u$ has at most one neighbor in $\{y_{1},y_{2}\}$ and $\{y_{3},y_{4}\}$ . Suppose $u\not\sim y_{2},u\not\sim y_{3}$ . Since both $y_{2},y_{3}$ are not adjacent to $v_{1}$ , $G[\{y_{3},u_{3},y_{2}\}\cup\{u,v_{1}\}]\simeq P_{3}\cup P_{2}$ , which causes contradiction. Therefore, $G[B_{2}]$ has at most one edge.

Suppose $B_{1}-A_{0}$ has no edge. Let $B_{2}=V_{1},B_{3}=V_{2},A_{0}=V_{3}$ , then we can apply claim3.3 to get $\chi(B_{1}\cup B_{2}\cup B_{3})\leq\chi(B_{1}-A_{0})+\chi(B_{2}\cup B_{3}\cup A_{0}\leq 4$ and hence $\chi(G)\leq\chi(B_{1}\cup B_{2}\cup B_{3})\leq 4+3=7$ .

case2: G is $\mathcal{Y}$ -free and contains a $co-tiwn-C_{5}$ .

According to observation 3, $V(G)=\{v_{1},v_{2}\}\cup(N(v_{2})\cup N(v_{1}))\cup M(v_{1},v_{2})$ .

Noticing that vertices in $N(v_{1})\cup N(v_{2})-\{v_{3},v_{5}\}$ have neighbor in $\{v_{4},v_{6}\}$ , we can divide $N(v_{1})\cup N(v_{2})-\{v_{3},v_{5}\}$ to make the structure more clearly. We difine two disjoint sets as following:

•

$D_{1}:=\{y|y\in N(v_{1})\cup N(v_{2})-\{v_{3},v_{5}\},y$ is adjacent to only one vertex in $\{v_{3},v_{4},v_{5},v_{6}\}\}$
•

$D_{2}:=\{y|y\in N(v_{1})\cup N(v_{2})-\{v_{3},v_{5}\},y$ is adjacent to more than one vertices in $\{v_{3},v_{4},v_{5},v_{6}\}\}$

$|D_{1}|=\emptyset$ . Otherwise, suppose $y_{1}\in D_{1}$ and $y_{1}\sim v_{1}$ . Suppose $y_{1}$ is adjacent to $\{v_{4}\}$ . Because if the only neighbor of $y_{1}$ belongs to $\{v_{3},v_{5}\}$ , then $G[\{v_{1},v_{2},y_{1},v_{4},v_{6}\}]$ induces $K_{3}\cup P_{2}$ or $P_{3}\cup P_{2}$ .

If $y_{1}$ is not adjacent to $v_{2}$ , then $G[\{v_{1},y_{1},v_{2},v_{3},v_{4},v_{5},v_{6}\}]$ is isomorphic to an element in $\mathcal{Y}$ (when $u_{1}$ is not adjacent to $u$ . However, if $y_{1}$ is not adjacent to $v_{2}$ , then $G[\{v_{1},y_{1},v_{2},v_{4},v_{5},v_{6}\}]\simeq co-domino$ . Therefore, such $y_{1}$ does not exist.

Any vertex in $D_{2}$ is complete to an edge in $G[\{v_{3},v_{4},v_{5},v_{6}\}]$ . Otherwise, there is $z\in D_{2}$ which is not complete to any edge in $G[\{v_{3},v_{4},v_{5},v_{6}\}]$ . $z$ must be adjacent to $\{v_{3},v_{5}\}$ , which leads to the contradiction that $G[\{v_{1},v_{2},z,v_{4},v_{6}\}]$ induces $K_{3}\cup P_{2}$ or $P_{2}\cup P_{3}$ .

$\{v_{1},v_{2}\}\cup M(v_{1},v_{2})$ can be colored with no more than $2$ colors.

Recalling that points in $D_{2}$ are at least adjacent to one edge in $G[\{v_{3},v_{4},v_{5},v_{6}\}]$ , it is trivial that $\chi(D_{2})\leq 5$ . In summary, $\chi(G)\leq\chi(\{v_{1},v_{2}\}\cup M(v_{1},v_{2}))+\chi(D_{2}\cup\{v_{3},v_{4},v_{5},v_{6}\})\leq 2+5\leq 7$ . ∎

Suppose all graphs are $(co-domino,K_{3}\cup P_{2},X_{1},X_{2},co-twin-C_{5})$ -free.

Let $C=u_{1}v_{1}v_{2}v_{3}u_{3}u_{2}$ be a $6$ -hole. We use $\chi 37$ to denote a graph obtained from $C$ by connecting edge $v1v3$ .

lemma 3.7.

If $G$ contains $\chi 37$ or $co$ - $A$ , then $\chi(G)\leq 7$ .

Proof.

case1: $G$ contains $\chi 37$ .

We prove $G[B_{2}]$ is edge-free. We obtain contradiction by proving $G[\{v_{1},v_{3},u_{1},u_{3},x_{1},x_{2}\}]\simeq co-twin-C_{5}$ . In other words, contradiction comes out if $x_{1},x_{2}$ are anticomplete to $\{u_{2}\}$ and complete to $\{u_{1},u_{3}\}$ . Suppose there is an edge in $G[B_{2}]$ and we call them $G[x_{1},x_{2}]$ . If $x_{1}$ (or $x_{2}$ ), $G[\{v_{1},v_{3}\}\cup\{x_{1},x_{2},u_{2}\}]$ would induce $K_{3}\cup P_{2}$ or $P_{3}\cup P_{2}$ . Furthermore, we can prove $\{x_{1},x_{2}\}$ is complete to $\{u_{1},u_{3}\}$ without much difficulty and hence we finish our proof of proposion that $G[B_{2}]$ is edge-free.

Furthermore, either $G[B_{3}]$ or $G[B_{1}-A_{0}]$ has no edge. Otherwise, suppose there is $\{y_{1},y_{2}\}\in E(B_{1}-A_{0})$ , $\{y_{3},y_{4}\}\in E(B_{3})$ . Since $B_{1}-A_{0}$ is complete to $\{u_{3}\}$ and anticomplete to $\{u_{1},u_{2}\}$ and $B_{3}$ is complete to $\{u_{1}\}$ and anticomplete to $\{u_{2},u_{3}\}$ , $G[y_{1},y_{3},u_{1},u_{3},u_{2},y_{2}]$ induces $co-domino$ or $co-twin-C_{5}$ .

According to claim3.3, $\chi(B_{1}\cup B_{3})\leq 3$ . Therefore, $\chi(G)\leq\chi(B_{2})+\chi(B_{1}\cup B_{3})+\chi(A_{2})\leq 7$ .

case2: $G$ is $\chi 37$ -free and contains a $co$ - $A$ .

$G[B_{2}]$ is complete to $\{v_{4},v_{6}\}$ and hence $G[B_{2}]$ is edge-free. Otherwise, there is $x\in B_{2}$ such that $x$ has only one neighbor in $\{v_{4},v_{6}\}$ . If $x\sim v_{4}$ , then $x\sim v_{5}$ . Otherwise, $G[\{v_{1},v_{2},x\}\cup\{v_{5},v_{6}\}]$ induces $P_{3}\cup P_{2}$ . However, $G[\{x,v_{2},v_{3},v_{6},v_{5},v_{1}\}]$ induces $\chi 37$ . Therefore, $x\sim v_{6}$ . Now $v\not\sim v_{5}$ , otherwise $G[\{v_{1},v_{2},v_{3},x,v_{6},v_{5}\}]$ induces $co-domino$ . However, $G[\{v_{1},v_{2},x,v_{6},v_{4},v_{5}\}]$ induces $co-A$ . Therefore, such $x$ does not exist.

every edge in $G[B_{1}-A_{0}]$ includes one vertex which is complete to $\{v_{4},v_{6}\}$ . Otherwise, there is an edge in $G[B_{1}-A_{0}]$ whose vertices has at most one neighbor in $\{v_{4},v_{6}\}$ . If one of them( $x$ ) is adjacent to $\{v_{4}\}$ rather than $\{v_{6}\}$ ,then $G[\{v_{2},v_{1},x\}\cup\{v_{5},v_{6}\}]$ induces $P_{3}\cup P_{2}$ . Therefore, none of these vertices is adjacent to $\{v_{4}\}$ and hence $G[\{v_{3},v_{4},v_{5}\}\cup B_{1}-A_{0}]$ induces $P_{3}\cup P_{2}$ . We already obtain a contradiction.

According to the above discussion, $G[(B_{1}-A_{0})\cup B_{2}]$ can be partitioned into two stable sets: the vertices which are complete to $\{v_{4},v_{6}\}$ and the rest of vertices in $B_{1}-A_{0}$ . Therefore, $\chi((B_{1}-A_{0})\cup B_{2})\leq 2$ .

Therefore, $\chi(G)\leq\chi(B_{2}\cup(B_{1}-A_{0}))+\chi(B_{3}\cup A_{0})+\chi(A_{2})\leq 2+2+3=7.$ ∎

Combining lemma3.4 and lemma3.7, we obtain theorem1.2 straightly.

theorem.

1.2 If $G$ contains $co-domino$ or $co-A$ , then $\chi(G)\leq 7$ .

Suppose $G$ is $(K_{3}\cup P_{2},co-domino,co-A)$ -free with $\overline{G[D_{1}]}$ is $P_{3}$ -free.

claim 3.8.

If $v_{1},v_{2}\in D_{1}$ and $v_{1}\not\sim v_{2}$ , then either $G[N(v_{1})-N(v_{2})]$ or $G[N(v_{2})-N(v_{1})]$ has no edge.

Proof.

Suppose both sets have edges. The vertex sets in $G[N(v_{1})-N(v_{2})]$ is $\{u_{1},u_{2}\}$ and that of edge in $G[N(v_{2})-N(v_{1})]$ is $\{u_{3},u_{4}\}$ . $G[\{v_{1},v_{2},u_{1},u_{2},u_{3},u_{4}\}]$ must induce $co-domino$ or $co-A$ or $P_{3}\cup P_{2}$ . Therefore, either $G[N(v_{1})-N(v_{2})]$ or $G[N(v_{2})-N(v_{1})]$ is edge-free. ∎

theorem.

(1.3) If $G[D_{2}]$ is not a clique, then $\chi(G)\leq$ 7.

Proof.

Since $G[D_{2}]$ is not a clique, $G[D_{2}]$ has two nonadjacent vertices $\{v_{1},v_{2}\}$ . According to claim3.8, either $G[N(v_{1})-N(v_{2})]$ or $G[N(v_{2})-N(v_{1})]$ has no edge. Without loss of generality, we suppose $G[N(v_{1})-N(v_{2})]$ is edge-free and hence $\chi(N(v_{1})\cup N(v_{2}))\leq 1$ .

If $\omega(N(v_{1})\cap N(v_{2}))\leq 1$ , then $\chi(N(v_{1})-N(v_{2}))\leq 1$ or $\chi(N(v_{2})-N(v_{1}))\leq 1$ . We suppose $\chi(N(v_{1})-N(v_{2}))\leq 1$ , then $\chi(v_{1})\leq 2$ . If $G[N(v_{1})]$ has edge( $\{v_{2},v_{3}\}$ ), then accoring to section 2.1, $G[\{v_{1},v_{2},v_{3}\}]$ can be divided into $B_{1}\cup B_{2}\cup B_{3}\cup(N(v_{1})\cap N(v_{2}))\cup(N(v_{1})\cap N(v_{3}))\cup(N(v_{2})\cap N(v_{3}))$ .

$\chi(N(v_{1}))\leq\chi(N(v_{1})\cap N(v_{2}))+\chi(N(v_{1})-N(v_{2}))\leq 2$ . The vertex sets left to be colored are: $A_{0},N(v_{2})\cap N(v_{3}),B_{2}$ and $B_{3}$ . Since $\chi(B_{2}\cup A_{0})\leq 2$ , $\chi(B_{3})\leq 2$ and $\chi(N(v_{2})\cap N(v_{3}))\leq 1$ . Therefore, $\chi(G)\leq 7.$

Suppose $\omega(N(v_{1})\cap N(v_{2}))=2$ .

We partition $V(G)$ into three parts: $\{v_{1},v_{2}\}$ , $N(v_{1})\cup N(v_{2})$ and $G-\{v_{1},v_{2}\}-N(v_{1})-N(v_{2})$ . Define $A:=G-\{v_{1},v_{2}\}-N(v_{1})-N(v_{2})$ .

$\chi(A)\leq 3$ . Suppose there is an edge( $x_{1}x_{2}$ ) in $G[A]$ . Then $A$ can be divided into $A-N(x_{1})$ and $(A-N(x_{2}))\cap N(x_{1})$ and $A\cap N(x_{1})\cap N(x_{2})$ . Since $A-N(x_{1})$ is anticomplete to $\{v_{1},x_{1},v_{2}\}$ and $G[\{v_{1},x_{1},v_{2}\}]\simeq P_{3}$ , $G[A-N(x_{1})]$ must be $P_{2}$ -free and hence $\chi(A-N(x_{1}))\leq 1$ . Similarly, $\chi((A-N(x_{2}))\cap N(x_{1}))\leq 1$ . Because $x_{1}\sim x_{2}$ and $\omega(G)\leq 3$ , $\chi(A\cap N(x_{1})\cap N(x_{2}))\leq 1$ . Therefore , $\chi(A)\leq 3$ .

$\chi(N(v_{2}))\leq 3$ . According to definition of $D_{2}$ , there is a $K_{3}(\{u_{1},u_{2},u_{3}\})$ induced in $G[G-N(v_{2})]$ . Define $E_{i}:=\{x\in N(v_{2})|x\text{ only adjacent to }\{u_{i}\}\}$ and $E_{i,j}:=\{x\in N(v_{2})|x\text{ only adjacent to }\{u_{i}\}\text{ and }\{u_{j}\}\}$ . Since $G$ is $co$ - $A$ -free, $E_{i}$ is anticomplete to $E_{i,i+1}$ (mod $3$ ). Obviously, $|E_{i}|\leq 1$ for $i=1,2,3$ and $G[E_{i,j}]$ is edge-free. Therefore $\chi(N(v_{2}))\leq\sum_{i=1}^{3}\chi(E_{i}\cup E_{i,i+1})\leq 3$ .

Because $\chi(N(v_{2}))\leq 3$ , $\chi(N(v_{2})\cup N(v_{1}))\leq\chi(N(v_{1})-N(v_{2}))+\chi(N(v_{2}))\leq 1+3=4$ . Consequently, $\chi(G)\leq\chi(N(v_{1})\cup N(v_{2}))+\chi(\{v_{1},v_{2}\}\cup A)\leq 4+3$ =7. ∎

Therefore, combining theorem1.1, theorem1.2 and theorem1.3, we obtain our major theorem.

theorem.

If $G$ is $(P_{3}\cup P_{2},K_{4})$ -free, then $\chi(G)\leq 7$ .

Finally, we prove a simple theorem using the above theorem.

theorem.

(1.4) If $G$ is $(4K_{1},\overline{P_{3}\cup P_{2}})$ -free with order $n$ and clique number $\omega$ , then $n\leq 7\omega$ and $\chi(G)\leq 4\omega$ .

Proof.

Suppose $G$ is $(4K_{1},\overline{P_{3}\cup P_{2}})$ -free.

If $\overline{G}$ is connected, then we apply the above theorem to obtain that $\chi(\overline{G})\leq 7$ . Therefore, $V(\overline{G})$ can be partitioned into $7$ stable sets and hence $V(G)$ can be partitioned into $7$ cliques. Therefore, $n\leq 7\omega$ .

If $\overline{G}$ is not connnected, then there is $G_{1}$ such that $G=G_{1}+G_{2}$ and hence $|V(G)|=|V(G_{1})|+|V(G_{2})|$ . Such decomposition will last until each $G_{i}$ satidfied $\overline{G_{i}}$ is connected. Suppose $G=G_{1}+...G_{k}$ . Since $V|G_{i}|\leq 7\omega(G_{i})$ and $\omega=\sum_{j=1}^{k}\omega(G_{i})$ , $|V(G)|=n\leq 7\omega$ .

It is trivial that the complement of bipartite graph is perfect graph. Therefore $V(G)$ can be partitioned into $3$ perfect graphs and one clique. Therefore, $\chi(G)\leq 4\omega$ .∎

4 acknowledge

I try to go further on $(P_{3}\cup P_{2},K_{4})$ -free graphs. However, I fail and 7 is the best upper bound I obtain. I know this is not a well-written paper. If you are confused about some details in the proof, you can email me at [email protected] or [email protected].

References

[1] A. Bharathi,S. Choudum. Colouring of $(P_{3}\cup P_{2})$ -free graphs.Graphs and Combinatorics 34(1):97–107,2018.
[2] L. Esperet, L. Lemoine, F. Maffray, and G. Morel. The chromatic number of $(P_{5},K_{4})$ -free
[3] A. Gyárfás. On ramsey covering numbers. Coll. Math. Soc. János Bolyai, 10:801–816, 1973. graphs. Discrete Math, 313:743–754, 2013.
[4] T. Karthick and S. Mishra. Coloring ( $P_{6}$ , diamond, $K_{4}$ )-free graphs.arXiv:1703.00606, 2017.
[5] Rui Li, Jinfeng Li and Di Wu. On the chromatic number of some ( $P_{3}\cup P_{2}$ )-free graphs, arXiv: 2308.15248, 2023.
[6] G. Serge and S. Huang. $(2P_{2},K_{4})$ -Free Graphs are 4-Colorable. SIAM Joural on Discrete Mathematics 33:1095–1120,2019.

A Note Related to Graph Theory

Abstract

1 Introduction

conjecture 1.1.

theorem 1.1.

theorem 1.2.

theorem 1.3.

theorem 1.4.

2 Structure Around K3K_{3}

3 main theorem

lemma 3.1.

claim 3.2.

theorem.

observation 1.

claim 3.3.

Proof.

observation 2.

lemma 3.4.

lemma 3.5.

observation 3.

lemma 3.6.

lemma 3.7.

theorem.

claim 3.8.

theorem.

theorem.

theorem.

4 acknowledge

References

2 Structure Around $K_{3}$