Equitable vertex arboricity of 5-degenerate graphs

Abstract

Wu et al. (Discret Math 313:2696–2701, 2013) conjectured that the vertex set of any simple graph G can be equitably partitioned into m subsets so that each subset induces a forest, where $\Delta (G)$ is the maximum degree of G and m is an integer with $m\ge \lceil \frac{\Delta (G)+1}{2}\rceil$. This conjecture is verified for 5-degenerate graphs in this paper.

1 Introduction

All graphs considered in this article are simple. Let G be a graph. We use V(G), E(G), |G|, $e(G),\Delta (G)$ and $\delta (G)$ to denote the vertex set, edge set, order, size, maximum degree and minimum degree of G, respectively. Denote by $G{\setminus } \{xy\}$ the graph obtained from G by deleting the edge xy but keeping two end vertices. For any vertex $v\in V(G)$, let $N_G(v)$ be the set of all neighbors of v in G. The degree of v, denoted by $d_G(v)$, is equal to $|N_G(v)|$. We use d(v) instead of $d_G(v)$ if no confusion arises. For two disjoint subsets U and W of V(G), the set of edges with one end in U and the other end in W is denoted by E(U, W) and $e(U,W)=|E(U,W)|$. In particular, $e(v,W)=d_{W}(v)$ denotes the number of neighbors of v in W. Define $N_{W}(u),u\in U$ as the set of neighbors of u in W and $N_{W}(U)=\bigcup \limits _{u\in U} N_{W}(u)$. We denote by G[U] the subgraph of G induced by U.

We associate positive integers $1,2,\ldots ,k$ with colors and call f a k-coloring of G if f is a mapping from V(G) to $\{1,2,\ldots ,k\}$. A k-coloring f of G is equitable if every color class has size $\lfloor \frac{|G|}{k}\rfloor$ or $\lceil \frac{|G|}{k}\rceil$. A coloring f is said to be proper if every two adjacent vertices receive different colors. The $equitable\ chromatic\ number$ of a graph G, denoted by $\chi _{=}(G)$, is the minimum integer k such that G has a proper equitable k-coloring. Note that a graph G which is equitably k-colorable may not be equitably $k'$-colorable for $k'>k$. The smallest k such that G has proper equitable colorings for any number of colors greater than or equal to k is called the $equitable\ chromatic\ threshold$ of G, and is denoted by $\chi _{\equiv }(G)$. Erdős (1964) conjectured that any graph with maximum degree $\Delta (G)\le r$ has a proper equitable $(r+1)$-coloring. The conjecture was proved by Hajnal and Szemerédi (1970). Recently, Kierstead and Kostochka (2008) gave a simpler proof of this theorem. There are two well-known conjectures regarding proper equitable colorings.

Conjecture 1

(Meyer 1973) For any connected graph G, $\chi _{=}(G)\le \Delta (G)$, with the exception that G is a complete graph or an odd cycle.

Conjecture 2

(Chen et al. 1994) For any connected graph G, $\chi _{\equiv }(G)\le \Delta (G)$, with the exception that G is a complete graph, an odd cycle or a complete bipartite graph $K_{2m+1,2m+1}$.

Note that Conjecture 2 is stronger than Conjecture 1 and has been verified for many classes of graphs, such as graphs with $\Delta (G)\le 4$, see Chen et al. (1994), Chen and Yen (2012) and Kierstead and Kostochka (2012) or $\Delta (G)\ge \frac{|G|}{3}+1$, see Chen et al. (1994), Chen and Yen (2012) and Yap and Zhang (1997), bipartite graphs (Lih and Wu 1996), outerplanar graphs (Yap and Zhang 1997), series-parallel graphs (Zhang and Wu 2011) and planar graphs with $\Delta (G)\ge 9$, see Zhang and Yap (1998) and Nakprasit (2012).

Here we consider a relaxed version of equitable coloring which is equitable tree-coloring. A k-coloring of a graph G is said to be a k-$tree\ coloring$ if the induced subgraph $G[V_i]$ is a forest, where $V_i$ denotes the set of vertices colored by i for each $i=1,2,\ldots ,k$. The $vertex\ arboricity$, or $point\ arboricity$ va(G) of a graph G is the minimum integer k such that G admits a k-tree coloring. It is proved that $va(G)\le \lceil \frac{\Delta (G)+1}{2}\rceil$ for any graph (Kronk and Mitchem 1975) and $va(G)\le 3$ for every planar graph (Chartrand and Kronk 1969). The minimum integer k such that G has an equitable k-tree coloring is the $equitable\ vertex\ arboricity$ of G, and is denoted by $va_{eq}(G)$. The $strong\ equitable\ vertex\ arboricity$ of G, denoted by $va_{eq}^{*}(G)$, is the smallest m such that G has an equitable $m'$-tree coloring for every $m'\ge m$. It is easy to see that $va_{eq}^{*}(G)\ge va_{eq}(G)$. In Wu et al. (2013), Wu, Zhang and Li posed the following conjectures.

Conjecture 3

(Wu et al. 2013) $va_{eq}^{*}(G)\le \lceil \frac{\Delta (G)+1}{2}\rceil$ for every graph G.

Conjecture 4

(Wu et al. 2013) There is a constant $\zeta$ such that $va_{eq}^{*}(G)\le \zeta$ for every planar graph G.

Conjecture 3 has been verified for graphs with $\Delta (G)\ge \frac{|V(G)|}{2}$ in Zhang and Wu (2014). In Wu et al. (2013), Wu, Zhang and Li proved that $va_{eq}^{*}(G)\le 3$ for every planar graph with $g(G)\ge 5$ and $va_{eq}^{*}(G)\le 2$ for every outerplanar graph and planar graph with $g(G)\ge 6$, where g(G) denotes the girth of G. Zhang in 2015 proved that $va_{eq}^{*}(G)\le 3$ for any planar graph such that all cycles of length at most 4 are independent and planar graph without 3-cycles and adjacent 4-cycles. Recently, Esperet, Lemoine and Maffray proved that $va_{eq}^{*}(G)\le 4$ for every planar graph G (Esperet et al. 2015), which confirms Conjecture 4.

A d-$degenerate\ graph$ is a graph G in which every subgraph has a vertex with degree at most d. In this paper, we confirm Conjecture 3 for 5-degenerate graphs. Clearly, since every planar graph has a vertex with degree at most 5, every planar graph is 5-degenerate. So the family of 5-degenerate graphs is a natural extension of the family of planar graphs. One strategy to tackle Conjecture 3 is to verify it for special classes of graphs. The family of planar graphs has been one of the candidates.

Theorem 5

Let G be a 5-degenerate graph. Then $va_{eq}^{*}(G)\le \lceil \frac{\Delta (G)+1}{2}\rceil$.

2 Proof of Theorem 5

Proof

$\square$

Claim 1

Let $m\ge 1$ be a fixed integer and ${\mathbb {G}}$ be the class of 5-degenerate graphs. Suppose that any graph G in ${\mathbb {G}}$ of order mt is equitably m-tree colorable for any integer $t\ge 1$. Then all graphs G in ${\mathbb {G}}$ are also equitably m-tree colorable.

Proof

We prove this Claim by induction on the order n of G. By the assumption, we may assume that $mt<n<m(t+1)$. If $m\le 2$, then $n=m(t+1)-1$. Now we consider the case that $m\ge 3$. Let $u\in V(G),d(u)=\delta (G)\le 5$. By the induction hypothesis, $G-u$ has an equitable m-tree coloring $\phi$. Let the color classes of $\phi$ be $V_1,V_2,\ldots ,V_m$, where $|V_i|=t$ or $t+1$ for all $i\ge 1$. Since $d(u)\le 5$, we assume each of $3,\ldots ,m$ appears at most once in the colors of N(u). If $|V_i|=t$ for some $i\ge 3$, then by adding u to $V_i$, we get an equitable m-tree coloring of G (having color classes $V_1,\ldots ,V_{i-1},V_i\bigcup \{u\},V_{i+1},\ldots ,V_m$). Hence we can assume that $|V_i|=t+1$ for all $i\ge 3$ and we also have $n=m(t+1)-1$. Let $G'=G\bigcup K_1$. Then $G'$ is a graph of order $m(t+1)$ and $\delta (G')\le 5$, thus by the assumption, $G'$ is equitably m-tree colorable (and so is G). $\square$

By Claim 1, we only need to show that $|G|=mt$, where $m\ge \lceil \frac{\Delta (G)+1}{2}\rceil$ and t are positive integers. We prove this theorem by induction on m. It is true for $m=1$ trivially. Now we consider the case when $m\ge 2$. Let G be an edge-minimal 5-degenerate graph that is not equitably m-tree colorable with $|G|=mt$. Let $x\in V(G)$ such that $d(x)=\delta (G)=d\le 5$. Let $x_1,x_2,\ldots , x_{d}\in N(x)$. By edge-minimality of G, the graph $G{\setminus } \{xx_1\}$ has an equitable m-tree coloring $\phi$ having color classes $V_1,V_2,\ldots ,V_m$. Then there exists a cycle C of G passing through the edge $xx_1$ such that all vertices on C are colored with the same color, for otherwise $\phi$ is also an equitable m-tree coloring of G. Without loss of generality, we assume that $x,x_1, x_2\in V_1$, $|N(x)\bigcap V_2|\le 2$, $|N(x)\bigcap V_i|\le 1(3\le i\le m)$. Let $V_1'=V_1{\setminus } (\{x\}\bigcup \{v\mid v\in V_1,N(v)\subseteq \bigcup \limits _{i=2}^{m}V_i\})$. Then $|V'_1|\le t-1$. Since $x_1, x_2\in V'_1$, $V'_1\ne \emptyset$. We say a vertex $v\in A$ is movable to a set B if $G[B\bigcup \{v\}]$ contains no cycle, otherwise v is not movable to B, where $A,B\subseteq V(G)$ and $A\bigcap B= \emptyset$. So if v is not movable to B, then $d_{B}(v)\ge 2$ and there is a vertex $u\in N_B(v)$ such that $d_B(u)\ge 1$.

We first consider the case when $\delta (G)\le 3$.

In this case, $|N(x)\bigcap V_i|\le 1(2\le i\le m)$. If for each $v\in \bigcup \limits _{i=2}^{m}V_i$, $d_{V_1'}(v)\ge 2$, then $e(\bigcup \limits _{i=2}^{m}V_i,V_1')\ge 2(m-1)t$. However, this contradicts with $e(\bigcup \limits _{i=2}^{m}V_i,V_1')\le (\Delta -1)(t-1)$ and $m\ge \lceil \frac{\Delta (G)+1}{2}\rceil$. Therefore, there exists $v\in V_i$ for some $i\in \{2,\ldots ,m\}$ such that $d_{V_1'}(v)\le 1$. Then we get an equitable m-tree coloring of G with color classes $(V_1{\setminus } \{x\})\bigcup \{v\},V_2,\ldots ,V_{i-1},(V_{i}{\setminus }\{v\})\bigcup \{x\},V_{i+1},\ldots , V_m$, a contradiction, too.

In the following, we deal with the case when $4\le \delta (G)\le 5$.

Claim 2

No vertex v in $\bigcup \limits _{i=3}^{m}V_i$ is movable to $V_1'$.

Proof

Suppose that there is $v\in V_i(3\le i\le m)$ which is movable to $V_1'$. Then we get an equitable m-tree coloring of G with color classes $(V_1{\setminus } \{x\})\bigcup \{v\},V_2,\ldots ,V_{i-1},(V_{i}{\setminus }\{v\})\bigcup \{x\},V_{i+1},\ldots , V_m$, a contradiction. $\square$

Claim 3

There exists a vertex $w\in V_2$ such that w is movable to $V_1'$.

Proof

By Claim 2, for each $v\in \bigcup \limits _{i=3}^{m}V_i$, $d_{V_1'}(v)\ge 2$. Hence $e(V_1', \bigcup \limits _{i=3}^{m}V_i)\ge 2(m-2)t$. Suppose that for any $w\in V_2$, w is not movable to $V_1'$, then $d_{V_1'}(w)\ge 2$ and $e(V_1',\bigcup \limits _{i=2}^{m}V_i)\ge 2(m-1)t$. This contradicts with $e(V_1',\bigcup \limits _{i=2}^{m}V_i)\le (\Delta -1)(t-1)$ and $m\ge \lceil \frac{\Delta (G)+1}{2}\rceil$. $\square$

Claim 4

No vertex v in $\bigcup \limits _{i=3}^{m}V_i$ is movable to $V_2'$, where $V_2'=V_2\backslash \{w\}$.

Proof

Suppose that there exists $v\in \bigcup \limits _{i=3}^{m}V_i$, such that v is movable to $V_2'$. Then we get an equitable m-tree coloring of G with color classes $(V_1{\setminus }\{x\})\bigcup \{w\},V_2'\bigcup \{v\},$ $V_3,\ldots ,V_{i-1},(V_i{\setminus }\{v\})\bigcup \{x\},V_{i+1},\ldots ,V_{m}$, a contradiction. $\square$

Case 1 $m=3$. Then $\Delta (G)\le 5$.

We say a vertex $z\in V_2'$ is replaceable by a vertex $y\in V_3$ if $yz\in E(G)$ and y is movable to $V_2'{\setminus } \{z\}$.

Claim 5

For every vertex $y\in V_3$, there is a vertex z in $V_2'$ such that z is replaceable by y.

Proof

For any $y\in V_3$, we know that $2\le d_{V_1'}(y)\le 3$ and $2\le d_{V_2'}(y)\le 3$. If $d_{V_2'}(y)=2$, any neighbor of y in $V_2'$ is replaceable by y. So assume that $d_{V_2'}(y)=3$ and $N_{V_2'}(y)=\{z_1,z_2,z_3\}$. If there is no path connecting $z_i$ and $z_j$ for some $i,j\in \{1,2,3\},i\ne j$, then $\{z_1,z_2,z_3\}{\setminus }\{z_i,z_j\}$ is replaceable by y. Therefore, there are paths $P_1,P_2,P_3$ connecting $z_1$ and $z_2$, $z_1$ and $z_3$, $z_2$ and $z_3$, respectively. Because $G[V_2']$ is a forest, there is a common vertex $z\in V(P_1)\bigcap V(P_2)\bigcap V(P_3)$. Then z is replaceable by y. $\square$

Claim 6

If $z\in V_2'$ is replaceable by a vertex $y\in V_3$, then z is not movable to $V_1'$.

Proof

Suppose that $z\in V_2'$ is replaceable by vertex $y\in V_3$ and z is movable to $V_1'$. Then we get an equitable 3-tree coloring of G with color classes $(V_1{\setminus } \{x\})\bigcup \{z\},(V_2{\setminus }\{z\})\bigcup \{y\},(V_3{\setminus }\{y\})\bigcup \{x\}$, a contradiction. $\square$

Since $|V_2'|\le t-1,|V_3|=t$, by Claim 5, there exists a vertex $z\in V_2'$ such that z is replaceable by at least two vertices in $V_3$. By Claim 6, $d_{V_1'}(z)\ge 2$ and $d_{V_2'}(z)\ge 1$. So $d_{V_3(z)}\le 2$. If z is replaceable by at least three vertices in $V_3$, then at least two of them, say $y_1,y_2$ are not adjacent. Note that there are paths connecting z to $y_1,y_2$, so z has at most neighbor in $V_3{\setminus } \{y_1,y_2\}$. Then we get an equitable 3-tree coloring with color classes $(V_1{\setminus } \{x\})\bigcup \{w\},(V_2{\setminus }\{z,w\})\bigcup \{y_1,y_2\},(V_3{\setminus }\{y_1,y_2\})\bigcup \{z,x\}$, a contradiction. Therefore, z is replaceable by exactly two vertices in $V_3$, say $y_1,y_2$. If $y_1y_2\not \in E(G)$ or $G[(V_2'{\setminus } \{z\})\bigcup \{y_1,y_2\}]$ is a forest, then we obtain an equitable 3-tree coloring of G as previously. So $y_1y_2\in E(G)$ and there exist $z_1,z_2\in V_2'$ such that either (a) $y_1z_1,y_2z_2\in E(G)$ and there is a path P connecting $z_1$ and $z_2$ or (b) $z_1=z_2$. If (a) holds, since z is replaceable by $y_1$ and $y_2$, there are paths $P_1,P_2$ connecting z to $z_1,z_2$ in $V_2'$, respectively. Since $G[V_2']$ is a forest, there is a vertex $z'\in V(P)\bigcap V(P_1)\bigcap V(P_2)$. If (b) holds, let $z_1=z_2=z'$. Since $d_{V_1'}(y_i)\ge 2$ and $y_1y_2\in E(G)$, hence $d_{V_2'}(y_i)=2,i=1,2$. So in both cases, $z'$ is replaceable by $y_1$ and $y_2$. If $z'$ is replaceable by $y_3\in V_3{\setminus } \{y_1,y_2\}$, then $y_1y_3\not \in E(G)$, we can get an equitable 3-tree coloring of G as previously, a contradiction. Hence $z'$ is not replaceable by any vertex in $V_3{\setminus }\{y_1,y_2\}$. This means that we can assign the vertices in $V_2'$ such that each of them is replaceable by at most one vertex in $V_3$. However, this contradicts with $|V_2'|<|V_3|$.

Case 2 $m\ge 4$.

Claim 7

For every vertex $v\in V_i,i\in \{3,\ldots ,m\}$, if $d_{V_2'}(v)=2$, then each vertex $u\in N_{V_2'}(v)$ is not movable to $V_1'$ and $d_{V_2'}(u)\ge 1$.

Proof

Suppose that there exists $u\in N_{V_2'}(v)$ which is movable to $V_1'$. Then we get an equitable m-tree coloring with color classes $(V_1{\setminus }\{x\})\bigcup \{u\},(V_2{\setminus }\{u\})\bigcup \{v\},V_3,\ldots ,V_{i-1},(V_{i}{\setminus }\{v\})\bigcup \{x\},V_{i+1},\ldots ,V_m$, a contradiction. By Claim 4, v is not movable to $V_2'$, so $d_{V_2'}(u)\ge 1$. $\square$

Define by $V_i'=\{v\in V_i\mid d_{V_2'}(v)=2\},i\in \{3,\ldots ,m\}$. Let $V_{k}'=\left\{ \begin{array}{cc} V_{m-1}', &{} \text{ if }\ |V_{m-1}'|\ge |V_{m}'|; \\ V_{m}', &{} \text{ otherwise }. \end{array} \right.$ We assume without loss of generality $V_{k}'=V_{m}'$.

Claim 8

$|V_m'|\ge 3$. Furthermore, there exists a vertex $z\in N_{V_2'}(V_{m}')$ such that $d_{V_m'}(z)\ge 3$.

Proof

Let $V_{21}'=\{v\in V_2'\mid v\in N_{V_2'}(\bigcup \limits _{i=3}^{m}V_i)\ \text{ and } v \text{ has } \text{ at } \text{ least } \text{ one } \text{ neighbor } \text{ in } V_2'{} \}$ and $V_{21}''=V_{21}'\bigcup \{v\in V_2'\mid \text{ there } \text{ is } \text{ a } \text{ path } \text{ connecting }\ v\ \text{ to }\ \text{ some } \text{ vertex }\ u\in V_{21}'\ \text{ in }\ V_{2}' \}$.

Suppose that $|V_m'|\le 2$. Then by the former arguments and Claim 7

$$\begin{aligned} \begin{aligned}\Delta (G)|V_{21}''|&\ge \sum \limits _{v\in V_{21}''}d(v) \\&\ge |V_{21}''|+2(m-4)t+2(|V_{m-1}'|+|V_{m}'|)+3(t-|V_{m-1}'|+t-|V_{m}'|)\\&+2\max \{|N_{V_2'}(V_{m-1}')|,|N_{V_2'}(V_{m}')|\}\\&\ge |V_{21}''|+(2m-2)t, \end{aligned} \end{aligned}$$

which is a contradiction with $m\ge \lceil \frac{\Delta (G)+1}{2}\rceil$ and $|V_{21}''|<t$.

Suppose that for any vertex $z\in N_{V_2'}(V_m')$ we have $d_{V_m'}(z)\le 2$. Since for each vertex $v\in V_m'$, $e(v,V_2')=2$, then $|N_{V_2'}(V_m')|\ge |V_{m}'|$. Therefore,

$$\begin{aligned} \begin{aligned}\Delta (G)|V_{21}''|&\ge \sum \limits _{v\in V_{21}''}d(v) \\&\ge |V_{21}''|+2(m-4)t+2(|V_{m-1}'|+|V_{m}'|)+3(t-|V_{m-1}'|+t-|V_{m}'|)\\&+2\max \{|N_{V_2'}(V_{m-1}')|,|N_{V_2'}(V_{m}')|\}\\&\ge |V_{21}''|+2(m-4)t+2(|V_{m-1}'|+|V_{m}'|)+3(t-|V_{m-1}'|+t-|V_{m}'|)+2|V_m'|\\&\ge |V_{21}''|+(2m-2)t, \end{aligned} \end{aligned}$$

which is a contradiction with $m\ge \lceil \frac{\Delta (G)+1}{2}\rceil$ and $|V_{21}''|<t$. $\square$

By Claim 8, there exists $z\in V_2'$ with $d_{V_m'}(z)\ge 3$. Since $G[V_m']$ is a forest, we assume that $y_1,y_2\in N_{V_{m}'}(z)$ and $y_1y_2\not \in E(G)$. Then $(V_1{\setminus }\{x\})\bigcup \{w\},(V_2{\setminus }\{z,w\})\bigcup \{y_1,y_2\}$ is an equitable 2-tree coloring of the graph $G[(V_1{\setminus }\{x\})\bigcup \{w\}\bigcup (V_2{\setminus }\{z,w\})\bigcup \{y_1,y_2\}]$. Let $G_1=G{\setminus } G[(V_1{\setminus }\{x\})\bigcup \{w\}\bigcup (V_2{\setminus }\{z,w\})\bigcup \{y_1,y_2\}]$. Then we can see that $\Delta (G_1)\le \Delta (G)-4=2(\frac{\Delta (G)+1}{2}-2)-1\le 2(m-2)-1$. Then we have $m-2\ge \lceil \frac{\Delta (G_1)+1}{2}\rceil$. By induction hypothesis, $G_1$ has an equitable $(m-2)$-tree coloring. So we can get an equitable m-tree coloring of G, a contradiction.

We complete the proof of the theorem.