The Hadwiger number, chordal graphs and ab-perfection

Peer review under responsibility of Kalasalingam University.

Research partially supported by CONACyT-Mexico, Grants 178395, 166306; PAPIIT-Mexico, Grant IN104915; a Postdoctoral fellowship of CONACyT-Mexico; and the National scholarship programme of the Slovak republic.

Abstract

A graph is chordal if every induced cycle has three vertices. The Hadwiger number is the order of the largest complete minor of a graph. We characterize the chordal graphs in terms of the Hadwiger number and we also characterize the families of graphs such that for each induced subgraph $H$, (1) the Hadwiger number of $H$ is equal to the maximum clique order of $H$, (2) the Hadwiger number of $H$ is equal to the achromatic number of $H$, (3) the $b$-chromatic number is equal to the pseudoachromatic number, (4) the pseudo-$b$-chromatic number is equal to the pseudoachromatic number, (5) the Hadwiger number of $H$ is equal to the Grundy number of $H$, and (6) the $b$-chromatic number is equal to the pseudo-Grundy number.

Keywords:

• Complete colorings
• Perfect graphs
• Forbidden graphs characterization

1 Introduction

Let $G$ be a finite graph. A $k$-coloring of $G$ is a surjective function $\varsigma$ that assigns a number from the set $\left[k\right]≔\{1,\dots ,k\}$ to each vertex of $G$. A $k$-coloring $\varsigma$ of $G$ is called proper if any two adjacent vertices have different colors, and $\varsigma$ is called complete if for each pair of different colors $i,j\in \left[k\right]$ there exists an edge $xy\in E\left(G\right)$ such that $x\in {\varsigma }^{-1}\left(i\right)$ and $y\in {\varsigma }^{-1}\left(j\right)$. A $k$-coloring $\varsigma$ of a connected graph $G$ is called connected if for all $i\in \left[k\right]$, each color class ${\varsigma }^{-1}\left(i\right)$ induces a connected subgraph of $G$.

The chromatic number $\chi \left(G\right)$ of $G$ is the smallest number $k$ for which there exists a proper $k$-coloring of $G$. The Hadwiger number $h\left(G\right)$ is the maximum $k$ for which a connected and complete coloring of a connected graph $G$ exists, and it is defined as the maximum $h\left(H\right)$ among the connected components $H$ of a disconnected graph $G$ (it is also known as the connected-pseudoachromatic number, see [1]).

A graph $H$ is called a minor of the graph $G$ if and only if $H$ can be formed from $G$ by deleting edges and vertices and by contracting edges. Suppose that $K_k$ is a minor of a connected graph $G$. If $V\left(K_k\right)=\left[k\right]$ then there exists a natural corresponding complete $k$-coloring $\varsigma :G\to \left[k\right]$ for which ${\varsigma }^{-1}\left(i\right)$ is exactly the set of vertices of $G$ which contract to vertex $i$ in $K_k$. The Hadwiger number $h\left(G\right)$ of a graph $G$ is the largest $k$ for which $K_k$ is a minor of $G$. Clearly,(1) $\omega \left(G\right)\le h\left(G\right)$(1) where $\omega \left(G\right)$ denotes the clique number of $G$: the maximum clique order of $G$.

The Hadwiger number was introduced by Hadwiger in 1943 [2] together the Hadwiger conjecture which states that $\chi \left(G\right)\le h\left(G\right)$ for any graph $G$.

The following definition is an extension of the notion of perfect graph, introduced by Berge [3]: Let $a,b$ be two distinct parameters of $G$. A graph $G$ is called $ab$-perfect if for every induced subgraph $H$ of $G$, $a\left(H\right)=b\left(H\right)$. Note that, with this definition a perfect graph is denoted by $\omega \chi$-perfect. The concept of the $ab$-perfect graphs was introduced by Christen and Selkow in [4] and extended in [5–10^{[5][6][7][8][9][10]}].

A graph $G$ without an induced subgraph $H$ is called $H$-free. A graph $H_1$-free, $H_2$-free, …is called $(H_1,H_2,\dots )$-free. A chordal graph is a $(C_4,C_5,\dots )$-free one.

Some known results are the following: Lóvasz proved in [11] that a graph $G$ is $\omega \chi$-perfect if and only if its complement is $\omega \chi$-perfect. Chudnovsky, Robertson, Seymour and Thomas proved in [12] that a graph $G$ is $\omega \chi$-perfect if and only if $G$ and its complement are $(C_5,C_7,\dots )$-free.

This paper is organized as follows: In Section 2 we prove that the families of chordal graphs and the family of $\omega h$-perfect graphs are the same. In Section 3, we give some consequences of Section 2 as characterizations of other graph families related to complete colorings.

2 Chordal graphs and $\omega h$-perfect graphs

We will use the following chordal graph characterization to prove Theorem 2.2:

Theorem 2.1

Hajnal, Surányi [13] and Dirac [14]

A graph $G$ is chordal if and only if $G$ can be obtained by identifying two complete subgraphs of the same order in two chordal graphs.

Now, we characterize the chordal graphs and the $\omega h$-perfect ones. The following proof is based on the standard proof of the chordal graph perfection (see [15]).

Theorem 2.2

A graph $G$ is $\omega h$-perfect if and only if $G$ is chordal.

Proof

Assume that $G$ is $\omega h$-perfect. Note that if a cycle $H$ is one of four or more vertices then $\omega \left(H\right)=2$ and $h\left(H\right)=3$. Hence, every induced cycle of $G$ has at the most $3$ vertices and the implication is true.

Now, we verify the converse. Since every induced subgraph of a chordal graph is also a chordal graph, it suffices to show that if $G$ is a connected chordal graph, then $\omega \left(G\right)=h\left(G\right)$. We proceed by induction on the order $n$ of $G$. If $n=1$, then $G=K_1$ and $\omega \left(G\right)=h\left(G\right)=1$. Assume, therefore, that $\omega \left(H\right)=h\left(H\right)$ for every induced chordal graph $H$ of order less than $n$ for $n\ge 2$ and let $G$ be a chordal graph of order $n$. If $G$ is a complete graph, then $\omega \left(G\right)=h\left(G\right)=n$. Hence, we may assume that $G$ is not complete. By Theorem 2.1, $G$ can be obtained from two chordal graphs $H_1$ and $H_2$ by identifying two complete subgraphs of the same order in $H_1$ and $H_2$. Let $S$ denote the set of vertices in $G$ that belong to $H_1$ and $H_2$. Thus the induced subgraph ${〈S〉}_G$ in $G$ by $S$ is complete and no vertex in $V\left(H_1\right)\setminus S$ is adjacent to a vertex in $V\left(H_2\right)\setminus S$. Hence, $\omega \left(G\right)=max\{\omega \left(H_1\right),\omega \left(H_2\right)\}=k\text{.}$ Moreover, according to the induction hypothesis, $\omega \left(H_1\right)=h\left(H_1\right)$ and $\omega \left(H_2\right)=h\left(H_2\right)$, then $max\{\omega \left(H_1\right),\omega \left(H_2\right)\}=max\{h\left(H_1\right),h\left(H_2\right)\}=k\text{.}$ On the other hand, since $S$ is a clique cut then each walk between $V\left(H_1\right)\setminus S$ and $V\left(H_2\right)\setminus S$ contains at least one vertex in $S$. Let $\varsigma$ be a pseudo-connected $h\left(G\right)$-coloring of $G$, and suppose there exist two color classes such that one is completely contained in $V\left(H_1\right)\setminus S$, and the other one is completely contained in $V\left(H_2\right)\setminus S$. Clearly these two color classes do not intersect, which contradicts our choice of $\varsigma$. Moreover, each color class with vertices both in $V\left(H_1\right)\setminus S$ and in $V\left(H_2\right)\setminus S$, contains vertices in $S$. Consequently, every pair of color classes having vertices both in $V\left(H_1\right)\setminus S$ and in $V\left(H_2\right)\setminus S$ must have an incidence in ${〈S〉}_G$. Thus, $h\left(G\right)\le max\{h\left(H_1\right),h\left(H_2\right)\}=k\text{.}$ By Eq. (1(1) $\omega \left(G\right)\le h\left(G\right)$(1) ), $\omega \left(G\right)=k=h\left(G\right)$ and the result follows.  □

It is known that every chordal graph is a $\omega \chi$-perfect one (see [15]). The following corollary is a consequence of the chordal graph perfection.

Corollary 2.3

Every $\omega h$-perfect graph is $\omega \chi$-perfect.

3 Other classes of $ab$-perfect graphs

In this section, we give a new characterization of several families of $ab$-perfect graphs related to complete colorings.

3.1 Achromatic and pseudoachromatic numbers

Firstly, the pseudoachromatic number $\psi \left(G\right)$ of $G$ is the largest number $k$ for which there exists a complete $k$-coloring of $G$ [16], and it is easy to see that (2) $\omega \left(G\right)\le h\left(G\right)\le \psi \left(G\right)\text{.}$(2) Secondly, the achromatic number $\alpha \left(G\right)$ of $G$ is the largest number $k$ for which there exists a proper and complete $k$-coloring of $G$ [17], and it is not hard to see that (3) $\omega \left(G\right)\le \alpha \left(G\right)\le \psi \left(G\right)\text{.}$(3) Complete bipartite graphs have achromatic number two (see [15]) but their Hadwiger number can be arbitrarily large, while the graph formed by the union of $K_2$ has Hadwiger number two but its achromatic number can be arbitrarily large. Therefore, $\alpha$ and $h$ are two non comparable parameters. We will use the following characterization in the proof of Corollary 3.2.

Theorem 3.1

Araujo-Pardo, R-M [5,6]

A graph $G$ is $\omega \psi$-perfect if and only if $G$ is $(C_4,P_4,P_3\cup K_2,3K_2)$-free.

Corollary 3.2 is an interesting result because it gives a characterization of two non comparable parameters.

Corollary 3.2

A graph $G$ is $\alpha h$-perfect if and only if $G$ is $\omega \psi$-perfect.

Proof

Since $h\left(C_4\right)=\alpha \left(P_4\right)=\alpha (P_3\cup K_2)=\alpha \left(3K_2\right)=3$ and $\alpha \left(C_4\right)=h\left(P_4\right)=h(P_3\cup K_2)=h\left(3K_2\right)=2$ (see Fig. 1) then a $\alpha h$-perfect graph is $(C_4,P_4,P_3\cup K_2,3K_2)$-free. By Theorem 3.1, $G$ is $\omega \psi$-perfect.

For the converse, if $G$ is $\omega \psi$-perfect, then by Eq. (2(2) $\omega \left(G\right)\le h\left(G\right)\le \psi \left(G\right)\text{.}$(2) ), $G$ is a $\omega h$-perfect graph, thus, the implication follows.  □

Fig. 1 Graphs with a complete coloring with numbers and a connected coloring with symbols.

Corollary 3.3

Every $\omega \psi$-perfect graph is $\omega \chi$-perfect.

Proof

If a graph $G$ is $\omega \psi$-perfect then Eq. (2(2) $\omega \left(G\right)\le h\left(G\right)\le \psi \left(G\right)\text{.}$(2) ) implies that $G$ is $\omega h$-perfect, and by Theorem 2.2$G$ is chordal, therefore $G$ is $\omega \chi$-perfect.  □

The following corollary is a consequence of the perfection of $\omega \psi$-perfect graphs.

Corollary 3.4

Every $\alpha h$-perfect graph is $\omega \chi$-perfect.

3.2 $b$-chromatic and pseudo-$b$-chromatic numbers

On one hand, a coloring such that every color class contains a vertex that has a neighbor in every other color class is called dominating. The pseudo-$b$-chromatic number $B\left(G\right)$ of a graph $G$ is the largest integer $k$ such that $G$ admits a dominating $k$-coloring.

On the other hand, the $b$-chromatic number $b\left(G\right)$ of $G$ is the largest number $k$ for which there exists a proper and dominating $k$-coloring of $G$ [7], therefore (4) $\omega \left(G\right)\le b\left(G\right)\le B\left(G\right)\le \psi \left(G\right)\text{.}$(4) We get the following characterizations:

Corollary 3.5

For any graph $G$the following are equivalent: $〈1〉$$G$ is $\omega \psi$-perfect, $〈2〉$$G$ is $b\psi$-perfect, $〈3〉$$G$ is $B\psi$-perfect and $〈4〉$$G$ is $(C_4,P_4,P_3\cup K_2,3K_2)$-free.

Proof

The proofs of $〈1〉\Rightarrow 〈2〉$ and $〈2〉\Rightarrow 〈3〉$ immediately follow from (4(4) $\omega \left(G\right)\le b\left(G\right)\le B\left(G\right)\le \psi \left(G\right)\text{.}$(4) ). To prove $〈3〉\Rightarrow 〈4〉$ note that, if $H\in \{C_4,P_4,P_3\cup K_2,3K_2\}$ then $B\left(H\right)\ne \psi \left(H\right)$, hence the implication is true, see Fig. 1. The proof of $〈4〉\Rightarrow 〈1〉$ is a consequence of Theorem 3.1.  □

The following corollary is a consequence of Corollaries 3.3 and 3.5.

Corollary 3.6

The $b\psi$-perfect graphs and the $B\psi$-perfect ones are $\omega \chi$-perfect.

Corollary 3.5 is related to the following theorem:

Theorem 3.7

Christen, Selkow [4] and Blidia, Ikhlef, Maffray [7]

For any graph $G$the following are equivalent: $〈1〉$$G$ is $\omega \alpha$-perfect, $〈2〉$$G$ is $b\alpha$-perfect and $〈3〉$$G$ is $(P_4,P_3\cup K_2,3K_2)$-free.

3.3 Grundy and pseudo-Grundy numbers

First, a coloring of $G$ is called pseudo-Grundy if each vertex is adjacent to some vertex of each smaller color. The pseudo-Grundy number $\gamma \left(G\right)$ is the maximum $k$ for which a pseudo-Grundy $k$-coloring of $G$ exists (see [18,15]).

Second, a proper pseudo-Grundy coloring of $G$ is called Grundy. The Grundy number $\Gamma \left(G\right)$ (also known as the first-fit chromatic number) is the maximum $k$ for which a Grundy $k$-coloring of $G$ exists (see [15,19]). From the definitions, we have that (5) $\omega \left(G\right)\le \Gamma \left(G\right)\le \gamma \left(G\right)\text{.}$(5) The following characterization of the graphs called trivially perfect graphs, will be used in the proof of Corollary 3.9.

Theorem 3.8

R-M [9]

A graph $G$ is $\omega \gamma$-perfect if and only if $G$ is $(C_4,P_4)$-free.

It is known that a trivially perfect graph is chordal (see [20]). The following corollary also gives a characterization of two non comparable parameters.

Corollary 3.9

A graph $G$ is $\Gamma h$-perfect if and only if $G$ is $\omega \gamma$-perfect.

Proof

A $\Gamma h$-perfect graph is $(C_4,P_4)$-free because $\Gamma \left(C_4\right)=h\left(P_4\right)=2$ and $\Gamma \left(P_4\right)=h\left(C_4\right)=3$ (see Fig. 1) then by Theorem 3.8, $G$ is $\omega \gamma$-perfect.

For the converse, let $G$ be a $\omega \gamma$-perfect graph. If $H$ is an induced graph of $G$, by Eq. (5(5) $\omega \left(G\right)\le \Gamma \left(G\right)\le \gamma \left(G\right)\text{.}$(5) ), $\omega \left(H\right)=\Gamma \left(H\right)$. Since $G$ is a chordal graph, $\omega \left(H\right)=h\left(H\right)$, so the implication follows.  □

The following corollary is a consequence of the perfection of $\omega \gamma$-perfect graphs.

Corollary 3.10

Every $\Gamma h$-perfect graph is $\omega \chi$-perfect.

3.4 The $b\gamma$-perfect graphs

Finally, we will use the following characterization of the proof of Theorem 3.12.

Theorem 3.11

Blidia, Ikhlef, Maffray [7]

A graph $G$ is $b\Gamma$-perfect if and only if $G$ is $(P_4,3P_3,2D)$-free.

We get the following characterization.

Theorem 3.12

A graph $G$ is $b\gamma$-perfect if and only if $G$ is $(C_4,P_4,3P_3,2D)$-free.

Proof

Note that, if $H\in \{C_4,P_4,3P_3,2D\}$ then $b\left(H\right)\ne \gamma \left(H\right)$, hence, the implication is true (see Fig. 1).

For the converse, a $(C_4,P_4,3P_3,2D)$-free graph $G$ is $\omega \gamma$-perfect (by Theorem 3.8) and $b\Gamma$-perfect (by Theorem 3.11). Then, for every induced subgraph $H$ of $G$, $\omega \left(H\right)=\gamma \left(H\right)=\Gamma \left(H\right)$ by Eq. (5(5) $\omega \left(G\right)\le \Gamma \left(G\right)\le \gamma \left(G\right)\text{.}$(5) ) and $b\left(H\right)=\Gamma \left(H\right)$. Therefore, $b\left(H\right)=\gamma \left(H\right)$ and the result follows.  □

Notes

Research partially supported by CONACyT-Mexico, Grants 178395, 166306; PAPIIT-Mexico, Grant IN104915; a Postdoctoral fellowship of CONACyT-Mexico; and the National scholarship programme of the Slovak republic.

Peer review under responsibility of Kalasalingam University.