Nordhaus-Gaddum problem in term of $G$ -free coloring

Yaser Rowshan¹ ¹Y. Rowshan, Department of Mathematics, Institute for Advanced Studies in Basic Sciences (IASBS), Zanjan 45137-66731, Iran [email protected]

Abstract.

Let $H=(V(H),E(H))$ be a graph. A $k$ -coloring of $H$ is a mapping $\pi:V(H)\longrightarrow\{1,2,\ldots,k\}$ , if each color class induces a $K_{2}$ -free subgraph. For a graph $G$ of order at least $2$ , a $G$ -free $k$ -coloring of $H$ , is a mapping $\pi:V(H)\longrightarrow\{1,2,\ldots,k\}$ , so that the induced subgraph by each color class of $\pi$ , contains no copy of $G$ . The $G$ -free chromatic number of $H$ , is the minimum number $k$ , so that it has a $G$ -free $k$ -coloring, and denoted by $\chi_{G}(H)$ . In this paper, we give some bounds and attributes on the $G$ -free chromatic number of graphs, in terms of the number of vertices, maximum degree, minimum degree, and chromatic number. Our main results are the Nordhaus-Gaddum-type theorem for the $\operatorname{\mathcal{G}}$ -free chromatic number of a graph.

Key words and phrases:

Conditional Chromatic number,

G

-free coloring, the Nordhaus-Gaddum problem,

G

-free critical.

2010 Mathematics Subject Classification:

05C15.

1. Introduction

Throughout this paper, all graphs are simple, undirected, and finite. For given graph $G$ , the vertex set, edge set, maximum degree, and minimum degree of $G$ , denoted by $V(G)$ , $E(G)$ , $\Delta(G)$ , and $\delta(G)$ , respectively. The number of vertices of $G$ is denoted by $|V(G)|$ . For a vertex $v\in V(G)$ , let $\deg_{G}{(v)}$ ( $\deg{(v)}$ ) and $N_{G}(v)$ denote the degree and neighbors of $v$ in $G$ , respectively. Let $W$ be any subset of $V(G)$ , the induced subgraph $G[W]$ , is the graph whose vertex set is $W$ and whose edge set consists of all of the edges in $E(G)$ that have both endpoints in $W$ . The join of two graphs $G$ and $H$ , denoted by $G+H$ , is a graph obtained from $G$ and $H$ by joining each vertex of $G$ to all vertices of $H$ .

1.1. $G$ -free coloring.

The conditional chromatic number $\chi(H,P)$ of $H$ , is the smallest integer $k$ , such that there exists a decomposition of $V(H)$ into sets $V_{1},\ldots,V_{k}$ , so that $H[V_{i}]$ satisfies the property $P$ , where $P$ is a graphical property, and $H[V_{i}]$ is the induced subgraph on $V_{i}$ , for each $1\leq i\leq k$ . This extension of graph coloring was presented by Harary in 1985 [4]. Suppose that $\operatorname{\mathcal{G}}$ be a family of graphs, when $P$ is the feature that a subgraph induced by each color class does not contain a copy of each member of $\operatorname{\mathcal{G}}$ , we write $\chi_{\operatorname{\mathcal{G}}}(H)$ instead of $\chi(H,P)$ . In this regard, we say a graph $H$ has a $\operatorname{\mathcal{G}}$ -free $k$ -coloring, if there exists a map $\pi:V(H)\longrightarrow\{1,2,\ldots,k\}$ , such that each color class $V_{i}=\pi^{-1}{(i)}$ does not contain any members of $\operatorname{\mathcal{G}}$ . For simplicity of notation if $\operatorname{\mathcal{G}}=\{G\}$ , then we write $\chi_{G}(H)$ instead of $\chi_{\operatorname{\mathcal{G}}}(H)$ .

An ordinary $k$ -coloring of $H$ can be viewed as $\operatorname{\mathcal{G}}$ -free $k$ -coloring of a graph $H$ by taking $\operatorname{\mathcal{G}}=\{K_{2}\}$ . It has been shown that for each graph $H$ , $\chi(H)\leq\Delta(H)+1$ . The well-known Brooks theorem, states that for any connected graph $H$ , if $H$ is neither an odd $C_{n}$ nor a $K_{n}$ , then $\chi(H)\leq\Delta(H)$ [2].

The Nordhaus-Gaddum problem [9], associates with the parameter $f(G)$ of a graph $H$ , and asks to find sharp bound for $f(H)+f(\overline{H})$ and $f(H)f(\overline{H})$ . Many authors have studied the Nordhaus-Gaddum problem, associate with the parameter $f(H)$ . Nordhaus and Gaddum in [9] investigate the $\chi(H)$ and $\chi(\overline{H})$ together, and they proved that if $H$ be a graph with $n$ members, then:

•

$2\sqrt{|V(H)|}\leq\chi(H)+\chi(\overline{H})\leq|V(H)|+1.$

After proving this theorem, inequalities containing the sum or product of a graph and its complement are called Nordhaus-Gaddum-type inequalities. The Nordhaus-Gaddum problem associated with the parameter $\chi_{n}(H)$ (The n-defective chromatic number), is to find sharp bounds for $\chi_{n}(H)+\chi_{n}(\overline{H})$ . Maddox [7] investigated this problem and showed that if $H$ be a $K_{3}$ -free graph, then:

•

$\chi_{n}(H)+\chi_{n}(\overline{H})\leq 5\lceil\frac{|V(H)|}{3n+3}\rceil.$

The domination number of a graph $H$ , denoted by $\gamma(H)$ , is the cardinality of the minimum dominating set. The general Nordhaus-Gaddum upper bounds for $\gamma(H)$ is given in [5] and it has proven that if $H$ be a graph whit $n$ members, then:

•

$3\leq\gamma(H)+\gamma(\overline{H})\leq|V(H)|+1.$

One can refer to[1] and [3, 8], and their references for further studies about the Nordhaus-Gaddum-type theorem. The vertex arboricity of graph $H$ , denoted by $a(H)$ , and defined as the minimum number of colors which are needed to color the vertices of $H$ , so that no cycle is monochromatic. The general Nordhaus-Gaddum upper bounds for vertex arboricity is given as follow:

Theorem 1.

[8]Let $H$ is a graph, then:

\lceil\sqrt{|V(H)|}\rceil\leq a(H)+a(\overline{H})\leq\frac{|V(H)|+3}{2}.

In this article, we prove some results for $\chi_{\operatorname{\mathcal{G}}}(H)$ . Our main results are the Nordhaus-Gaddum-type theorem for the $\operatorname{\mathcal{G}}$ -free chromatic number of a graph as follows.

Theorem 2.

Suppose that $\operatorname{\mathcal{G}}$ is a family of graphs with minimum degrees $\delta(\operatorname{\mathcal{G}})$ , where $\delta(\operatorname{\mathcal{G}})=\min\{\delta(G):~{}G\in\operatorname{\mathcal{G}}\}$ . Also, assume that $H$ is a graph with $n(H)$ vertices. Then, we have:

\chi_{\operatorname{\mathcal{G}}}(H)+\chi_{\operatorname{\mathcal{G}}}(\overline{H})\leq\left\{\begin{array}[]{ll}\lceil\frac{n(H)}{\delta(\operatorname{\mathcal{G}})}\rceil+1&~{}~{}~{}~{}when~{}\operatorname{\mathcal{G}}=\operatorname{\mathcal{C}}~{}or~{}either,~{}~{}H~{}or~{}\overline{H}~{}is~{}\operatorname{\mathcal{G}}-free~{}critical,\vspace{.2 cm}{}\\ \lceil\frac{n(H)}{\delta(G)}\rceil+2&~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}otherwise.\end{array}\right.

In Theorem 2, if we take $\operatorname{\mathcal{G}}=\{K_{2}\}$ , then we get Nordhaus-Gaddum’s result. Also, if we take $\operatorname{\mathcal{G}}=\operatorname{\mathcal{C}}$ , then we get Theorem 1.

2. Main results

To prove Theorem 2, we need some theorems and lemmas. In this section, we give some properties of $G$ -free coloring, and some upper bounds on the $G$ -free chromatic number of graphs.

2.1. Some properties and some bounds of $G$ -free coloring of graphs.

$k$ -critical graphs have a key role in studying ordinary graph coloring. Here we define the $G$ -free $k$ -critical graphs.

Definition 3.

A graph $H$ with $\chi_{G}(H)=k$ is said $G$ -free $k$ -critical, if for each proper subgraph $H^{\prime}$ of $H$ , $\chi_{G}(H^{\prime})\leq k-1$ .

Let $H$ be a graph with $\chi_{G}(H)=k$ . By taking a minimal subgraph of $H$ with $G$ -free chromatic number $k$ , it is easy to say that this subgraph is $G$ -free $k$ -critical. It is well known that if $H$ be a $k$ -critical graph with $\chi(H)=k$ , then $\delta(H)\geq\chi(H)-1$ . As a generalization, we have the following result:

Lemma 4.

If $H$ is a $G$ -free $k$ -critical graph, then:

\delta(H)\geq\delta(G)(k-1).

Proof.

By contradiction, let there exists a vertex of $V(H)$ say $x$ , such that $\deg(x)\leq\delta(G)(k-1)-1$ . Since $H$ is $G$ -free $k$ -critical, so $\chi_{G}(H\setminus x)\leq k-1$ . Set $H^{\prime}=H\setminus x$ . Without loss of generality(w.l.g) suppose that $V_{1},V_{2},\ldots,V_{k-1}$ is a partition of $V(H^{\prime})$ , so that $H^{\prime}[V_{i}]$ is $G$ -free. Since $\deg(x)\leq\delta(G)(k-1)-1$ , so there is at least one $j\in[k-1]$ , such that $|N(x)\cap V_{j}|\leq\delta(G)-1$ . Hence $H[V_{j}\cup\{x\}]$ is a $G$ -free subgraph of $H$ . Thus, $\chi_{G}(H)\leq k-1$ , a contradiction. ∎

Now we present some upper bounds on $\chi_{G}(H)$ . In [10] Szekeres and Wilf have shown that $\chi(H)\leq 1+\max\delta(H^{\prime})$ , where $H^{\prime}\subseteq H$ . In the next theorem, we extend the Szekeres and Wilf theorem.

Theorem 5.

Let $G$ be a given graph. For an arbitrary graph $H$ , we have:

\chi_{G}(H)\leq 1+\lceil\frac{\max\delta(H^{\prime})}{\delta(G)}\rceil.

where the maximum is taken over all induced subgraphs $H^{\prime}\subseteq H$ .

To prove the next corollary, we need the following theorem by Lovász.

Theorem 6.

[6] If $d_{i}\geq d_{i+1}$ for $1\leq i\leq k$ , where $k$ is a positive integer, such that $\sum\limits^{i=k}_{i=1}d_{i}\geq\Delta(G)-k+1$ , then $V(G)$ can be decomposed into $k$ classes $V_{i}$ ( $~{}i=1,\ldots,k$ ), such that $\Delta(G[V_{i}])\leq d_{i}$ for each $i=1,2,\ldots,k$ .

Corollary 7.

Let $H$ and $G$ be two graphs with maximum degrees $\Delta(H)$ and $\Delta(G)$ , respectively. Then:

\chi_{G}(H)\leq\lceil\frac{\Delta(H)+1}{\Delta(G)}\rceil.

Proof.

It is easy to show that $\chi_{G}(H)\leq\chi_{K_{2}}(H)=\chi(H)\leq\Delta(H)+1$ . Hence, if $\Delta(G)=1$ , then the corollary holds. Let $\Delta(G)\geq 2$ . If $\Delta(H)\leq\Delta(G)-1$ , then $H$ has no copy of $G$ and $\chi_{G}(H)=1$ . Assume that $\Delta(H)=k\Delta(G)+r$ , where $k\geq 1$ and $r\in[\Delta-1]$ . For $1\leq i\leq k+1$ , we set $d_{i}=\Delta(G)-1$ . Hence:

	$\displaystyle d_{1}+d_{2}+\ldots+d_{k+1}$	$\displaystyle=(k+1)(\Delta(G)-1)$
		$\displaystyle\geq k\Delta(G)-k+r$
		$\displaystyle=\Delta(H)-(k+1)+1.$

By Theorem 6, $V(H)$ can be decomposed into classes $V_{1},V_{2},\ldots,V_{k+1}$ , such that $\Delta(H[V_{i}])\leq\Delta(G)-1$ for each $i\in[k+1]$ , and as a consequence $H[V_{i}]$ is $G$ -free. Therefore:

\chi_{G}(H)\leq k+1=\lceil\frac{\Delta(H)+1}{\Delta(G)}\rceil.

∎

It should be mentioned that the same bound was proved for the defective chromatic number of graphs, by Frick and Henning.

Proposition 8.

Let $H$ and $G$ be two graphs. Then:

\chi_{G}(H)\leq\lceil\frac{\chi(H)}{\chi(G)-1}\rceil.

Note that this bound is sharp for $G\cong H$ , $G\cong K_{n+1}$ and $H\cong K_{kn+1}$ or $G=K_{2}$ and $H$ is an odd cycle or $K_{n}$ .

Lemma 9.

For each graph $H$ with $\chi_{G}(H)=k$ , $H$ has a subgraph say $F$ , such that $F$ is a $G$ -free $k$ -critical graph

Lemma 10.

For any integers $m,n$ , where $n\leq m$ , and any two graphs $H$ and $G$ with $\chi_{G}(H)=m$ , $H$ has a subgraph say $F$ , such that $\chi_{G}(F)=n$ .

Proof.

For $n=0$ , the result is trivial. Suppose that $1\leq n\leq m$ , and $\chi_{G}(H)=m$ . By Lemma 9, $H$ has a subgraph say $F$ , such that $\chi_{G}(F)=m$ . If $n=m$ , the result holds, otherwise let $v\in V(F)$ , hence $\chi_{G}(F\setminus\{v\})=m-1$ . So by induction, there is a $G$ -free $n$ -critical subgraph of both $F\setminus\{v\}$ and $H$ , hence the proof is complete. ∎

By Lemma 10, it is easy to check that for each $G$ -free $n$ -critical graph $H$ , if $F$ is a $G$ -free subgraph of $H$ , then $\chi_{G}(H\setminus F)=n-1$ .

2.2. Proof of theorem 2.

In [9], Nordhaus and Gaddum showed that for each graph $H$ with $n$ vertices, $\chi(H)+\chi(\overline{H})\leq n+1$ . In the following results, we extend the Nordhaus and Gaddum-problem. To simplify the comprehension, let us split the proof of Theorem 2 into small parts. We begin with a very useful general upper bound in the following theorem:

Theorem 11.

Let $H$ and $G$ be two graphs, where $\delta(G)=\delta$ , $|V(H)|=n$ . If $G\cong K_{\delta+1}$ , then $n\neq k\delta(k,\delta\geq 3)$ , and if $G\ncong K_{\delta+1}$ , then $H$ is critical. Hence:

(I):

$\chi_{G}(H)+\chi_{G}(\overline{H})\leq\lceil\frac{n}{\delta}\rceil+1$ ,
(II):

This bound is sharp.

Proof.

(I). By induction on $n$ , when $n\leq|G|-1$ , (I) holds. Suppose that $n\geq|V(G)|$ and consider the following cases:

Case1 : $G\ncong K_{\delta+1}$ . Assume that $\chi_{G}(H)=t_{1}$ and $\chi_{G}(\overline{H})=t_{2}$ . We shall show that $t_{1}+t_{2}\leq\lceil\frac{n}{\delta}\rceil+1$ . As $H$ is $G$ -free $t_{1}$ -critical, for each $v\in V(H)$ , we have $\chi_{G}(H\setminus\{v\})\leq t_{1}-1$ . So, Theorem 6 implies that $\delta(H)\geq(t_{1}-1)\delta$ . Let $v$ be a vertex of $V(H)$ . Hence, by induction assumption we have:

(1)

\chi_{G}(H\setminus\{v\})+\chi_{G}(\overline{H}\setminus\{v\})\leq\lceil\frac{n-1}{\delta}\rceil+1.

Now we have a claim as follow:

Claim 2: $\chi_{G}(\overline{H})\leq\lceil\frac{n}{\delta}\rceil-t_{1}+1$ .
Since $\chi_{G}(H\setminus\{v\})\leq t_{1}-1$ and $\delta(H)\geq(t_{1}-1)\delta$ , it yields that $\Delta(\overline{H})=n-1-\delta(H)\leq n-1-(t_{1}-1)\delta$ . Hence by Corollary 7, we have:

\chi_{G}(\overline{H})\leq\lceil\frac{\Delta(\overline{H})+1}{\delta}\rceil\leq\lceil\frac{n-(t_{1}-1)\delta}{\delta}\rceil=\lceil\frac{n}{\delta}\rceil-(t_{1}-1).

Now, by Claim $2$ , $t_{1}+\chi_{G}(\overline{H})\leq\lceil\frac{n}{\delta}\rceil+1$ . Therefore, $\chi_{G}(H)+\chi_{G}(\overline{H})\leq\lceil\frac{n}{\delta}\rceil+1$ , and the proof of Case $1$ is complete.

Case 2 : $G\cong K_{\delta+1}$ . As $G\cong K_{\delta+1}$ and $n\neq k\delta$ , one can check that $\omega(H)\geq\delta+1$ and $\omega(\overline{H})\geq\delta+1$ , otherwise either $H$ is $G$ -free or $\overline{H}$ is $G$ -free, then by this fact that $\chi_{G}(H)\leq\lceil\frac{n(H)}{\delta}\rceil$ , the proof is complete. Hence, suppose that $V^{\prime}=\{v_{1},v_{2},\ldots,v_{\delta+1}\},V^{\prime\prime}=\{v^{\prime}_{1},v^{\prime}_{2},\ldots,v^{\prime}_{\delta+1}\}\subseteq V(H)$ , where $H[V^{\prime}]\cong K_{\delta+1}$ and $\overline{H}[V^{\prime\prime}]\cong K_{\delta+1}$ . As, $H[V^{\prime}]\cong K_{\delta+1}$ and $\overline{H}[V^{\prime\prime}]\cong K_{\delta+1}$ , by considering $V^{\prime}\cap V^{\prime\prime}$ , one can say that $|V^{\prime}\cap V^{\prime\prime}|\leq 1$ . Therefore, there exists $W^{\prime}\subseteq V^{\prime}$ and $W^{\prime\prime}\subseteq V^{\prime\prime}$ , so that $|W^{\prime}|=|W^{\prime\prime}|=\delta$ , $W^{\prime}\cap W^{\prime\prime}=\emptyset$ , $H[W^{\prime}]\cong K_{\delta}$ and $\overline{H}[W^{\prime\prime}]\cong K_{\delta}$ . Set $W=W^{\prime}\cup W^{\prime\prime}$ . Now, we have a claim as follow:

Claim 3: $|\omega(H[W])|\leq\delta+1$ , $|\omega(\overline{H}[W]|\leq\delta+1$ and $|\omega(H[W])|+|\omega(\overline{H}[W]|\leq 2\delta+1$ .
As, $H[W^{\prime}]\cong K_{\delta}$ and $\overline{H}[W^{\prime\prime}]\cong K_{\delta}$ , so $\delta\leq|\omega(H[W])|\leq\delta+1$ , $\delta\leq|\omega(\overline{H}[W]|\leq\delta+1$ . Now, by contrary, suppose that $|\omega(H[W])|=|\omega(\overline{H}[W]|=\delta+1$ . As $|\omega(H[W])|=\delta+1$ , there exists a vertex of $W^{\prime\prime}$ say $v^{\prime\prime}$ , such that $W^{\prime}\subseteq N_{H}(v^{\prime\prime})$ . Since $|\omega(\overline{H}[W]|=\delta+1$ , there exists a vertex of $W^{\prime}$ say $v^{\prime}$ , such that $W^{\prime\prime}\subseteq N_{\overline{H}}(v^{\prime})$ , a contradiction to $W^{\prime}\subseteq N_{H}(v^{\prime\prime})(v^{\prime}v^{\prime\prime}\in E(H))$ . Hence, $|\omega(H[W])|+|\omega(\overline{H}[W]|\leq 2\delta+1$ .

Set $H_{1}=H[V\setminus W]$ . Now, by induction hypothesis:

(2)

\chi_{G}(H_{1})+\chi_{G}(\overline{H}_{1})\leq\lceil\frac{n(H_{1})}{\delta}\rceil+1=\lceil\frac{n-2\delta}{\delta}\rceil+1=\lceil\frac{n}{\delta}\rceil-1.

And by Claim 3:

(3)

\chi_{G}(H[W])+\chi_{G}\overline{H}[W]\leq 3.

If $|\omega(H[W])|=|\omega(\overline{H})[W]|=\delta$ , then $\chi_{G}(H[W])+\chi_{G}\overline{H}[W]=2$ , that is $H[W]$ and $\overline{H}[W]$ are $G$ -free. So 2 implies that, $\chi_{G}(H)+\chi_{G}(\overline{H})\leq\lceil\frac{n}{\delta}\rceil+1$ . Hence, we may suppose that $\chi_{G}(H[W])+\chi_{G}\overline{H}[W]=3$ . If strict inequality holds in $(\ref{e7})$ , then by using $(\ref{e8})$ , we have:

(4)

\chi_{G}(H)+\chi_{G}(\overline{H})\leq\chi_{G}(H_{1})+\chi_{G}(\overline{H_{1}})+3\leq\lceil\frac{n}{\delta}\rceil+1.

Now, suppose that inequality holds in both $(\ref{e7})$ and $(\ref{e8})$ , and by Claim 3, w.l.g suppose that $|\omega(H[W])|=\delta+1$ and $|\omega(\overline{H})[W]|=\delta$ . Since, $|\omega(H[W])|=\delta+1$ , so there exists at least one vertex of $W^{\prime\prime}$ say $v^{\prime\prime}$ , such that $W^{\prime}\subseteq N_{H}(v^{\prime\prime})$ . Set $v\in W^{\prime}$ , $H_{2}=H_{1}\cup\{v\}$ .

Now, since $|W|=2\delta$ and $|V(H)|\neq k\delta$ , so $|V(H_{1})|\neq k^{\prime}\delta$ . Therefore, as $\chi_{G}(H_{1})+\chi_{G}(\overline{H_{1}})=\lceil\frac{n}{\delta}\rceil-1$ , and $|V(H_{1})|\neq k^{\prime}\delta$ , one can check that $\lceil\frac{n}{\delta}\rceil=\lceil\frac{n+1}{\delta}\rceil$ . Now, by the induction hypothesis, $\chi_{G}(H_{2})+\chi_{G}(\overline{H_{2}})=\lceil\frac{n}{\delta}\rceil-1$ . Since $v\in W^{\prime}$ and $|\omega(\overline{H}[W]|=\delta$ , so $|\omega(H[W\setminus\{v\}])|=\delta$ and $|\omega(\overline{H}[W\setminus\{v\}]|\leq\delta$ . That is:

\chi_{G}(H[W\setminus\{v\}])+\chi_{G}\overline{H}[W\setminus\{v\}]=2.

Now, as $\chi_{G}(H_{2})+\chi_{G}(\overline{H_{2}})=\lceil\frac{n}{\delta}\rceil-1$ , we can check that $\chi_{G}(H)+\chi_{G}(\overline{H})\leq\chi_{G}(H_{2})+\chi_{G}(\overline{H_{2}})+2=\lceil\frac{n}{\delta}\rceil+1$ , and the proof is complete.

Now by Cases 1, 2 the proof of (I) is complete. To prove (II), consider the following cases:

Case 1: $G\ncong K_{\delta+1}$ .
In this case, set $H=K_{4,4}$ and $G=H$ . As, $G=H$ , and $\overline{H}=2K_{4}$ is $G$ -free, thus $\chi_{G}(H)=2$ , $\chi_{G}(\overline{H})=1$ , that is, $\chi_{G}(H)+\chi_{G}(\overline{H})=2+1=3=\lceil\frac{8}{4}\rceil+1$ .

By setting $H=G=C_{5}$ . As, $H=\overline{H}=G=C_{5}$ , so $\chi_{G}(H)+\chi_{G}(\overline{H})=2+2=4=\lceil\frac{5}{2}\rceil+1$ .

Case 2: $G\cong K_{\delta+1}$ , and $|V(H)|\neq k\delta$ , $k,\delta\geq 3$ .
Consider the graph $H$ , where $|V(H)|=kd+1$ , $H\cong K_{(k-1)d}+(\delta+1)K_{1}$ and $\overline{H}\cong K_{\delta+1}$ . As $G\cong K_{\delta+1}$ , and $\overline{H}\cong K_{\delta+1}$ , thus $\chi_{G}(\overline{H})=2$ . Now, we would like to show that $\chi_{G}(H)=k$ . By definition of $H$ , one can check that $|\omega(H[W])|=(k-1)d+1$ . Suppose that, $V=V(H)=\{v_{1},v_{2},\ldots,v_{k\delta+1}\}$ , $V^{\prime}=\{v_{1},\ldots,v_{(k-1)\delta}\}$ , where $H[V^{\prime}]\cong K_{(k-1)\delta}$ and $H[V\setminus V^{\prime}]\cong(\delta+1)K_{2}$ . It is easy to say that $\chi_{G}(H)\leq k$ , by considering $V_{1},V_{2},\ldots,V_{k}$ as a coloring classes of $V(H)$ , where $V_{i}\subseteq V^{\prime}$ , $|V_{i}|=\delta$ for each $1\leq i\leq k-1$ and $V_{k}=V(H)\setminus V^{\prime}$ . Since $|V_{i}|=d$ , for $1\leq i\leq k-1$ , and $\omega(H[V_{k}])=1$ , so $H[V_{i}]$ is $G$ -free, and $\chi_{G}(H)\leq k$ . Also, since $|\omega(H)|=(k-1)\delta+1$ and $G\cong K_{\delta+1}$ , it can be checked that $\chi_{G}(H)\geq k$ . Therefore, $\chi_{G}(H)=k$ and $\chi_{G}(H)+\chi_{G}(\overline{H})=k+2=\lceil\frac{n}{\delta}\rceil+1$ . Which implies that the proof is complete. ∎

With an argument similar to Claim 3, one can say that if $H$ and $G$ be two graphs, where $G\cong K_{d+1}$ , and $|V(H)|=2d$ , then:

\chi_{G}(H)+\chi_{G}(\overline{H})\leq 3=\lceil\frac{n}{d}\rceil+1.

Also, if $H$ and $G$ be two graphs, where $G\ncong K_{d+1}$ , and $|V(G)|=d+2$ , then:

\chi_{G}(H)+\chi_{G}(\overline{H})\leq\lceil\frac{n}{d}\rceil+2.

Lemma 12.

Let $H$ and $G$ be two graphs, where $\delta(G)=\delta$ , $|V(H)|=n$ , $G\ncong K_{d+1}$ , and $H$ is not a critical graph. Hence:

\chi_{G}(H)+\chi_{G}(\overline{H})\leq\lceil\frac{n}{\delta}\rceil+2.

Proof.

By induction on $n$ , when $n\leq|G|-1$ , the lemma holds. Suppose that $n\geq|V(G)|$ , $\chi_{G}(H)=t_{1}$ and $\chi_{G}(\overline{H})=t_{2}$ . We shall show that $t_{1}+t_{2}\leq\lceil\frac{n}{\delta}\rceil+2$ . By Lemma 9, $H$ has a $G$ -free $t_{1}$ -critical subgraph. Assume that $F$ is a $t_{1}$ -critical subgraph of $H$ with $|V(F)|=n_{1}\leq n-1$ . Let $V_{1}=V(H)\setminus V(F)$ and $|V_{1}|=n_{2}$ . W.l.g suppose that $V_{1}=\{v_{1},v_{2}\ldots,v_{n_{2}}\}$ . As $F$ is a $t_{1}$ -critical, so by Theorem 11,

(5)

\chi_{G}(F)+\chi_{G}(\overline{F})\leq\lceil\frac{n_{1}}{\delta}\rceil+1.

Since $F$ is $G$ -free $t_{1}$ -critical subgraph of $H$ , then $\chi_{G}(H)=\chi_{G}(F)=t_{1}$ . Let $\chi_{G}(\overline{H}[V(F)])=t_{3}$ . Hence:

(6)

\chi_{G}(F)+\chi_{G}(\overline{F})=\chi_{G}(H)+\chi_{G}(\overline{H}[V(F)])=t_{1}+t_{3}\leq\lceil\frac{n_{1}}{\delta}\rceil+1.

We note that $\chi_{G}(\overline{H})\leq\chi_{G}(\overline{H}[V(F)])+\chi_{G}(\overline{H}[V_{1}])$ . Now we can partition the vertices of $V_{1}$ into $m$ sets with size at most $\delta+1$ , say $W_{1},W_{2},\ldots,W_{m}$ . Since $G\ncong K_{\delta+1}$ , thus $|V(G)|\geq\delta+2$ , that is $\overline{H}[W_{i}]$ is $G$ -free. So, $\chi_{G}(\overline{H}[V_{1}])\leq\lceil\frac{n_{2}}{\delta+1}\rceil\leq\lceil\frac{n_{2}}{\delta}\rceil$ . Hence $\chi_{G}(\overline{H})\leq t_{3}+\chi_{G}(\overline{H}[V_{1}])$ . That is:

\chi_{G}(H)+\chi_{G}(\overline{H})\leq\lceil\frac{n}{\delta}\rceil+2.

Which means that the proof is complete. ∎

In the next theorem, we determine an upper bound for $\chi_{G}(H)+\chi_{G}(\overline{H})$ , where $G\cong K_{d+1}$ , and $|V(H)|=kd(k,d\geq 3)$ . Also, we characterize certain classes of graphs with better upper bound.

Theorem 13.

Suppose that $H$ and $G$ be two graphs, where $G\cong K_{d+1}$ , and $|V(H)|=kd(k,d\geq 3)$ , then:

\chi_{G}(H)+\chi_{G}(\overline{H})\leq k+2.

And if:

(I):

Either, $H$ or $\overline{H}$ is $G$ -free critical.
(II):

There exists a subset of $V(H)$ say $S$ , with size $2d$ , such that $H[S]$ and $\overline{H}[S]$ is $G$ -free.
(III):

There exists a subset of $V(H)$ say $S$ , with size $2d$ , such that either $g(H[S])=2d$ or $g(\overline{H}[S])=2d$ .

Where, $g(H)$ is the girth of $H$ and is defined as the size of the smallest cycle in $H$ . Then:

\chi_{G}(H)+\chi_{G}(\overline{H})\leq k+1.

Proof.

With an argument similar to Theorem 11, one can say that:

\chi_{G}(H)+\chi_{G}(\overline{H})\leq k+2.

Now, to prove (I), w.l.g we may suppose that $H$ is $G$ -free critical, that is for each $v\in V(H)$ , $\chi_{G}(H\setminus\{v\})\leq\chi_{G}(H)-1$ . Let $v$ be a vertex of $V(H)$ . Hence, by Theorem 11,

(7)

\chi_{G}(H\setminus\{v\})+\chi_{G}(\overline{H}\setminus\{v\})\leq\lceil\frac{n-1}{\delta}\rceil+1.

As, $H$ is $G$ -free critical, $\delta(H)\geq(\chi_{G}(H)-1)\delta$ , it yields $\Delta(\overline{H})=n-1-\delta(H)\leq n-1-(\chi_{G}(H)-1)\delta$ . Hence, by Corollary 7,

\chi_{G}(\overline{H})\leq\lceil\frac{\Delta(\overline{H})+1}{\delta}\rceil\leq\lceil\frac{n-(\chi_{G}(H)-1)\delta}{\delta}\rceil=\lceil\frac{n}{\delta}\rceil-(\chi_{G}(H)-1).

Therefore, $\chi_{G}(H)+\chi_{G}(\overline{H})\leq\lceil\frac{n}{\delta}\rceil+1$ and the proof of (I) is complete.

We prove (II) by induction on $k$ . For $k=3$ , it is clear that $\chi_{G}(H)+\chi_{G}(\overline{H})\leq k+1$ . For $k=4$ , as $H[S]$ , $\overline{H}[S]$ are $G$ -free, and $|S|=2k$ , so $\chi_{G}(H[S])+\chi_{G}(\overline{H})[S]=2$ . Hence, with an argument similar to Claim 3, either $H[\overline{S}]$ is $G$ -free or $\overline{H}[\overline{S}]$ is $G$ -free. So, $\chi_{G}(H[\overline{S}])+\chi_{G}(\overline{H})[\overline{S}]\leq 3$ and $\chi_{G}(H)+\chi_{G}(\overline{H})\leq 5=k+1$ . Now, let for each $k^{\prime}\leq k-1$ the statement holds, and suppose that $H$ be a graph with $kd$ vertices. W.l.g assume that $S$ with size $2d$ be a subset of $V(H)$ , where $H[S]$ and $\overline{H}[S]$ are $G$ -free. Set $H^{\prime}=H\setminus S$ , Hence, $|H^{\prime}|=(k-2)d$ , and by induction, $\chi_{G}(H^{\prime})+\chi_{G}(\overline{H^{\prime}})\leq k-1$ . As, $H[S]$ and $\overline{H}[S]$ are $G$ -free, thus $\chi_{G}(H)+\chi_{G}(\overline{H})\leq k+1$ .

To prove (III), w.l.g we may suppose that $S$ with size $2d$ is a subset of $V(H)$ , such that $g(H[S])=2d$ . As, $g(H[S])=2d$ , $d\geq 3$ , and $G=K_{d+1}$ , so $H[S]$ is $G$ -free. Since $g(H[S])=2d$ , so $\overline{H}[S]\cong K_{2d}\setminus C_{2d}$ , and $\omega(\overline{H}[S])=d$ , that is $\overline{H}[S]$ is $G$ -free. Therefore, by proof of (II), the proof of (III) is complete.

Which implies that the proof is complete. ∎

Assume that $\operatorname{\mathcal{C}}$ is a family of all $2$ -regular graphs. In the next theorem, we determine an upper bound for $\chi_{G}(H)+\chi_{G}(\overline{H})$ , for each $G\in\operatorname{\mathcal{C}}$ .

Theorem 14.

Let $H$ and $G$ be two graphs, where $G\in\operatorname{\mathcal{C}}$ , hence:

\chi_{G}(H)+\chi_{G}(\overline{H})\leq\lceil\frac{n}{2}\rceil+1.

And this bound is sharp.

Proof.

Case 1: $G=K_{3}$ . If $|V(H)\neq 2k$ for each $k\geq 3$ , then the proof is complete by Theorem 11. So, suppose that $|V(H)=2k$ for some $k\geq 1$ . We prove by induction. For $k=1,2$ it is clear that $\chi_{K_{3}}(H)+\chi_{K_{3}}(\overline{H})\leq k+1$ . Suppose that $\chi_{K_{3}}(H)+\chi_{K_{3}}(\overline{H})\leq k^{\prime}+1$ , for each $k^{\prime}\leq k-1$ , and assume that $H$ be a graph with $2k$ vertices, where $k\geq 3$ . Assume that $v,v^{\prime}$ be two vertices of $H$ , where $\deg_{H}(v)=\deg_{H}(v^{\prime})$ . Set $H^{\prime}=H\setminus\{v,v^{\prime}\}$ , as $|V(H^{\prime})|=2(k-1)$ , by induction $\chi_{K_{3}}(H^{\prime})+\chi_{K_{3}}(\overline{H^{\prime}})\leq k$ . If $\chi_{K_{3}}(H^{\prime})+\chi_{K_{3}}(\overline{H^{\prime}})\leq k-1$ , then the proof is complete. Hence, assume that $\chi_{K_{3}}(H^{\prime})+\chi_{K_{3}}(\overline{H^{\prime}})=k$ . If either $\chi_{K_{3}}(H^{\prime})=\chi_{K_{3}}(H)$ or $\chi_{K_{3}}(\overline{H^{\prime}})=\chi_{K_{3}}(\overline{H})$ , then the proof is same. Now, suppose that $\chi_{K_{3}}(H)=\chi_{K_{3}}(H^{\prime})+1$ and $\chi_{K_{3}}(\overline{H})=\chi_{K_{3}}(\overline{H^{\prime}})+1$ . In other word, suppose that adding $x$ to $H^{\prime}$ and $x^{\prime}$ to $\overline{H^{\prime}}$ increases the $\chi_{K_{3}}(H^{\prime})$ and $\chi_{K_{3}}(\overline{H^{\prime}})$ by one, where $x,x^{\prime}\in\{v,v^{\prime}\}$ . Now we have a claim as follow:

Claim 4: $x\neq x^{\prime}$ . By contrary, suppose that $x=x^{\prime}$ , $\chi_{K_{3}}(H^{\prime})=t_{1}$ and $\chi_{K_{3}}(\overline{H^{\prime}})=t_{2}$ , where $t_{1}+t_{2}=k$ . As $\chi_{K_{3}}(H^{\prime}\cup\{x\})=t_{1}+1$ and $\chi_{K_{3}}(\overline{H^{\prime}}\cup\{x\})=t_{2}+1$ , we can say that $|N_{H}(x)|\geq 2t_{1}$ and $|N_{\overline{H}}(x)|\geq 2t_{2}$ . Now, $2k-1=|N_{H}(x)|+|N_{\overline{H}}(x)|\geq 2(t_{1}+t_{2})$ , that is $2k\leq 2k-1$ , a contradiction.

So, suppose that $x=v$ and $x=v^{\prime}$ . Since $\chi_{K_{3}}(H^{\prime}\cup\{v\})=t_{1}+1$ and $\chi_{K_{3}}(\overline{H^{\prime}}\cup\{v^{\prime}\})=t_{2}+1$ , so $|N_{H}(v)|\geq 2t_{1}$ and $|N_{\overline{H}}(v^{\prime})|\geq 2t_{2}$ . As $\deg_{H}(v)=\deg_{H}(v^{\prime})$ , thus $n-1=2k-1=|N_{H}(v)|+|N_{\overline{H}}(v^{\prime})|\geq 2(t_{1}+t_{2})$ , that is $2k\leq 2k-1$ , a contradiction again. Hence, we can say that $\chi_{K_{3}}(H^{\prime})+\chi_{K_{3}}(\overline{H^{\prime}})\leq k-1$ , or $\chi_{K_{3}}(H^{\prime})=\chi_{K_{3}}(H)$ , or $\chi_{K_{3}}(\overline{H^{\prime}})=\chi_{K_{3}}(\overline{H})$ , in any case, $\chi_{K_{3}}(H)+\chi_{K_{3}}(\overline{H})\leq k+1$ .

Case 2: $G=C_{m}$ , $m\geq 4$ . For the case that $|V(H)|=2k$ , the proof is same as the Case 1. Hence assume that $|V(H)|=2k+1$ for some $k\geq 2$ . We prove by induction. For $k=1,2$ it is clear that $\chi_{C_{m}}(H)+\chi_{C_{m}}(\overline{H})\leq k+1$ . Suppose that $\chi_{C_{m}}(H)+\chi_{C_{m}}(\overline{H})\leq k^{\prime}+1$ for each $k^{\prime}\leq k-1$ , and assume that $H$ be a graph with $2k+1$ vertices, where $k\geq 3$ . Assume that $V^{\prime}=\{v_{1},v_{2},v_{3}\}$ be a subsets of $V(H)$ . Set $H^{\prime}=H\setminus V^{\prime}$ , as $|V(H^{\prime})|=2(k-1)$ , by induction, $\chi_{C_{m}}(H^{\prime})+\chi_{C_{m}}(\overline{H^{\prime}})\leq k$ . Also as $|V(G)|=m\geq$ , so $H[V^{\prime}]$ and $\overline{H}[V^{\prime}]$ are $G$ -free. Therefore, $\chi_{C_{m}}(H)+\chi_{C_{m}}(\overline{H})\leq\chi_{C_{m}}(H^{\prime})+1+\chi_{C_{m}}(\overline{H^{\prime}})+1\leq k+2=\lceil\frac{n}{2}\rceil+1$ , and the proof of Case 2 is complete.

To prove the sharpness of the bound, set $H=K_{3}+3K_{1}$ , that is $\overline{H}=K_{3}$ . Hence, $\chi_{K_{3}}(H)=\chi_{K_{3}}(\overline{H})=2$ . Therefore, as $|V(H)|=6$ , so $\chi_{K_{3}}(H)+\chi_{K_{3}}(\overline{H})=4=\lceil\frac{6}{2}\rceil+1$ . Which implies that the proof is complete.

∎

Therefore by Theorems 11, 13, and 14, we have a result as follow:

Theorem 15.

\chi_{\operatorname{\mathcal{G}}}(H)+\chi_{\operatorname{\mathcal{G}}}(\overline{H})\leq\left\{\begin{array}[]{ll}\lceil\frac{n(H)}{\delta(\operatorname{\mathcal{G}})}\rceil+1&~{}~{}~{}~{}when~{}\operatorname{\mathcal{G}}=\operatorname{\mathcal{C}}~{}or~{}either,~{}~{}H~{}or~{}\overline{H}~{}is~{}\operatorname{\mathcal{G}}-free~{}critical,\vspace{.2 cm}{}\\ \lceil\frac{n(H)}{\delta(G)}\rceil+2&~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}otherwise.\end{array}\right.

Proof.

Suppose that $G\in\operatorname{\mathcal{G}}$ , clearly $\chi_{\operatorname{\mathcal{G}}}(H)\leq\max_{G\in\operatorname{\mathcal{G}}}\chi_{G}(H)$ . Assume that $\max_{G\in\operatorname{\mathcal{G}}}\chi_{G}(H)=\chi_{G^{\prime}}(H)$ , and $\delta^{\prime}=\delta(G^{\prime})$ . Hence, $\chi_{\operatorname{\mathcal{G}}}(H)\leq\chi_{G^{\prime}}(H)$ . Since $\delta(\operatorname{\mathcal{G}})\leq\delta^{\prime}$ and by Theorems 11, 13 and 14, one can check that $\chi_{\operatorname{\mathcal{G}}}(H)\leq\chi_{G^{\prime}}(H)\leq\lceil\frac{n(H)}{\delta^{\prime}}\rceil+i\leq\lceil\frac{n(H)}{\delta(\operatorname{\mathcal{G}})}\rceil+i$ , where $i\in\{1,2\}$ . Which implies that the proof is complete.

∎

In Theorem 2, if we take $\operatorname{\mathcal{G}}=\{K_{2}\}$ , then we get Nordhaus-Gaddum’s result in terms of chromatic number. Also, assume that $\operatorname{\mathcal{C}}$ is a family of all $2$ -regular graphs. One can see for a given graph $H$ , $a(H)$ and $\chi_{\operatorname{\mathcal{C}}}(H)$ are identical. Therefore, if we take $\operatorname{\mathcal{G}}=\operatorname{\mathcal{C}}$ , then by Theorem 2, we get Theorem 1.

References

[1] Mustapha Aouchiche and Pierre Hansen. A survey of nordhaus–gaddum type relations. Discrete Applied Mathematics, 161(4-5):466–546, 2013.
[2] R. L. Brooks. On colouring the nodes of a network. Proc. Cambridge Philos. Soc., 37:194–197, 1941.
[3] Jason I Brown and R Hoshino. Nordhaus–gaddum inequalities for the fractional and circular chromatic numbers. Discrete mathematics, 309(8):2223–2232, 2009.
[4] Frank Harary. Conditional colorability in graphs. In Graphs and applications (Boulder, Colo., 1982), Wiley-Intersci. Publ., pages 127–136. Wiley, New York, 1985.
[5] François Jaeger and Charles Payan. Relations du type nordhaus-gaddum pour le nombre d’absorption d’un graphe simple. CR Acad. Sci. Ser. A, 274:728–730, 1972.
[6] L. Lovász. On decomposition of graphs. Studia Sci. Math. Hungar., 1:237–238, 1966.
[7] Randall B Maddox. Vertex partitions and transition parameters. 1989.
[8] John Mitchem. On the point-arboricity of a graph and its complement. Canadian Journal of Mathematics, 23(2):287–292, 1971.
[9] E.A Nordhaus and Jerry W Gaddum. On complementary graphs. The American Mathematical Monthly, 63(3):175–177, 1956.
[10] George Szekeres and Herbert S Wilf. An inequality for the chromatic number of a graph. Journal of Combinatorial Theory, 4(1):1–3, 1968.

Nordhaus-Gaddum problem in term of GG-free coloring

Abstract.

Key words and phrases:

2010 Mathematics Subject Classification:

1. Introduction

1.1. GG-free coloring.

Theorem 1.

Theorem 2.

2. Main results

2.1. Some properties and some bounds of GG-free coloring of graphs.

Definition 3.

Lemma 4.

Proof.

Theorem 5.

Theorem 6.

Corollary 7.

Proof.

Proposition 8.

Lemma 9.

Lemma 10.

Proof.

2.2. Proof of theorem 2.

Theorem 11.

Proof.

Lemma 12.

Proof.

Theorem 13.

Proof.

Theorem 14.

Proof.

Theorem 15.

Proof.

References

Nordhaus-Gaddum problem in term of $G$ -free coloring

1.1. $G$ -free coloring.

2.1. Some properties and some bounds of $G$ -free coloring of graphs.