Search

The {\em square} of a graph $G$, denoted $G^2$, has the same vertex set as $G$ and has an edge between two vertices if the distance between them in $G$ is at most $2$. In general, $\Delta(G) + 1 \leq \chi(G^2) \leq \Delta(G)^2 +1$ for every graph $G$. Charpentier [1] asked whether $\chi(G^2) \leq 2 \Delta(G)$ if $mad(G) < 4$. But Hocquard, Kim, and Pierron [6] answered his question negatively. For every even value of $\Delta(G)$, they constructed a 2-degenerate graph $G$ such that $\omega(G^2) = \frac{5}{2} \Delta(G)$. Note that if $G$ is a 2-degenerate graph, then $mad(G) < 4$. Thus, we have that \[ {\displaystyle \frac{5}{2} \Delta(G) \leq \max \{\chi(G^2) : G \mbox{ is a 2-degenerate graph} \} \leq 3 \Delta(G) +1}. \] So, it was naturally asked whether there exists a constant $D_0$ such that $\chi(G^2) \leq \frac{5}{2} \Delta(G)$ if $G$ is a 2-degenerate graph with $\Delta(G) \geq D_0$. Recently Cranston and Yu [3] showed that $\omega(G^2) \leq \frac{5}{2} \Delta(G)+72$ if $G$ is a 2-degenerate graph, and $\omega(G^2) \leq \frac{5}{2} \Delta(G)+60$ if $G$ is a 2-degenerate graph with $\Delta(G) \geq 1729$. We show that there exists a constant $D_0$ such that $\omega(G^2) \leq \frac{5}{2} \Delta(G)$ if $G$ is a 2-degenerate graph with $\Delta(G) \geq D_0$. This upper bound on $\omega(G^2)$ is tight by the construction in [6]., Comment: 32 pages

The square of a graph $G$, denoted $G^2$, has the same vertex set as $G$ and has an edge between two vertices if the distance between them in $G$ is at most $2$. Thomassen (2018) and Hartke, Jahanbekam and Thomas (2016) proved that $\chi(G^2) \leq 7$ if $G$ is a subcubic planar graph. A natural question is whether $\chi_{\ell}(G^2) \leq 7$ or not if $G$ is a subcubic planar graph. Cranston and Kim (2008) showed that $\chi_{\ell}(G^2) \leq 7$ if $G$ is a subcubic planar graph of girth at least 7. We prove that $\chi_{\ell}(G^2) \leq 7$ if $G$ is a subcubic planar graph of girth at least 6., Comment: 9 pages, 1 figure

For a graph $H$, a graph $G$ is $H$-saturated if $G$ does not contain $H$ as a subgraph but for any $e \in E(\overline{G})$, $G+e$ contains $H$. In this note, we prove a sharp lower bound for the number of paths and walks on length $2$ in $n$-vertex $K_{r+1}$-saturated graphs. We then use this bound to give a lower bound on the spectral radii of such graphs which is asymptotically tight for each fixed $r$ and $n\to\infty$.

In this paper, we show the following three theorems. Let $G$ be a $K_5$-minor-free graph. Then Alon-Tarsi number of $G$ is at most $5$, there exists a matching $M$ of $G$ such that the Alon-Tarsi number of $G-M$ is at most $4$, and there exists a forest $F$ such that the Alon-Tarsi number of $G-E(F)$ is at most $3$., Comment: 12 pages,2 figures

An $r$-dynamic $k$-coloring of a graph $G$ is a proper $k$-coloring such that for any vertex $v$, there are at least $\min\{r, deg_G(v) \}$ distinct colors in $N_G(v)$. The $r$-dynamic chromatic number $\chi_r^d(G)$ of a graph $G$ is the least $k$ such that there exists an $r$-dynamic $k$-coloring of $G$. The list $r$-dynamic chromatic number of a graph $G$ is denoted by $ch_r^d(G)$. Loeb et al. $[11]$ showed that $ch_3^d(G)\leq 10$ for every planar graph $G$, and there is a planar graph $G$ with $\chi_3^d(G)= 7$. In this paper, we study a special class of planar graphs which have better upper bounds of $ch_3^d(G)$. We prove that $ch_3^d(G) \leq 6$ if $G$ is a planar graph which is near-triangulation, where a near-triangulation is a planar graph whose bounded faces are all 3-cycles.

DP-coloring (also known as correspondence coloring) is a generalization of list coloring, introduced by Dvo\v{r}\'ak and Postle in 2017. It is well-known that there are non-4-choosable planar graphs. Much attention has recently been put on sufficient conditions for planar graphs to be DP-$4$-colorable. In particular, for each $k \in \{3, 4, 5, 6\}$, every planar graph without $k$-cycles is DP-$4$-colorable. In this paper, we prove that every planar graph without $7$-cycles and butterflies is DP-$4$-colorable. Our proof can be easily modified to prove other sufficient conditions that forbid clusters formed by many triangles., Comment: 11 pages, 6 figures

This paper constructs a planar graph $G_1$ such that for any subgraph $H$ of $G_1$ with maximum degree $\Delta(H) \le 3$, $G_1-E(H)$ is not $3$-choosable, and a planar graph $G_2$ such that for any star forest $F$ in $G_2$, $G_2-E(F)$ contains a copy of $K_4$ and hence $G_2-E(F)$ is not $3$-colourable. On the other hand, we prove that every planar graph $G$ contains a forest $F$ such that the Alon-Tarsi number of $G - E(F)$ is at most $3$, and hence $G - E(F)$ is 3-paintable and 3-choosable., Comment: 12 pages, 5 figures

A proper vertex $k$-coloring of a graph $G=(V,E)$ is an assignment $c:V\to \{1,2,\ldots,k\}$ of colors to the vertices of the graph such that no two adjacent vertices are associated with the same color. The square $G^2$ of a graph $G$ is the graph defined by $V(G)=V(G^2)$ and $uv \in E(G^2)$ if and only if the distance between $u$ and $v$ is at most two. We denote by $\chi(G^2)$ the chromatic number of $G^2$, which is the least integer $k$ such that a $k$-coloring of $G^2$ exists. By definition, at least $\Delta(G)+1$ colors are needed for this goal, where $\Delta(G)$ denotes the maximum degree of the graph $G$. In this paper, we prove that the square of every graph $G$ with $\text{mad}(G)<4$ and $\Delta(G) \geqslant 8$ is $(3\Delta(G)+1)$-choosable and even correspondence-colorable. Furthermore, we show a family of $2$-degenerate graphs $G$ with $\text{mad}(G)<4$, arbitrarily large maximum degree, and $\chi(G^2)\geqslant \frac{5\Delta(G)}{2}$, improving the result of Kim and Park., Comment: 14 pages, 4 figures

DP-coloring (also known as correspondence coloring) of a simple graph is a generalization of list coloring. It is known that planar graphs without 4-cycles adjacent to triangles are 4-choosable, and planar graphs without 4-cycles are DP-4-colorable. In this paper, we show that planar graphs without 4-cycles adjacent to triangles are DP-4-colorable, which is an extension of the two results above., Comment: 15 pages, 5 figures

DP-coloring of a simple graph is a generalization of list coloring, and also a generalization of signed coloring of signed graphs. It is known that for each $k \in \{3, 4, 5, 6\}$, every planar graph without $C_k$ is 4-choosable. Furthermore, Jin, Kang, and Steffen \cite{JKS} showed that for each $k \in \{3, 4, 5, 6\}$, every signed planar graph without $C_k$ is signed 4-choosable. In this paper, we show that for each $k \in \{3, 4, 5, 6\}$, every planar graph without $C_k$ is 4-DP-colorable, which is an extension of the above results.

Dvo\v{r}\'{a}k and Postle \cite{DP} introduced a \textit{DP-coloring} of a simple graph as a generalization of a list-coloring. They proved a Brooks' type theorem for a DP-coloring, and Bernshteyn, Kostochka and Pron \cite{BKP} extended it to a DP-coloring of multigraphs. However, detailed structure when a multigraph does not admit a DP-coloring was not specified in \cite{BKP}. In this note, we make this point clear and give the complete structure. This is also motivated by the relation to signed coloring of signed graphs.

Let $k$ and $\ell$ be positive integers. A cycle with two blocks $c(k,\ell)$ is an oriented cycle which consists of two internally (vertex) disjoint directed paths of lengths at least $k$ and $\ell$, respectively, from a vertex to another one. A problem of Addario-Berry, Havet and Thomass\'e (2007) asked if, given positive integers $k$ and $\ell$ such that $k+\ell\ge 4$, any strongly connected digraph $D$ containing no $c(k,\ell)$ has chromatic number at most $k+\ell-1$. In this paper, we show that such digraph $D$ has chromatic number at most $O((k+\ell)^2)$, improving the previous upper bound $O((k+\ell)^4)$ obtained by Cohen, Havet, Lochet and Nisse (2016). In fact, we are able to find a digraph which shows that the answer to the above problem is no. We also show that if in addition $D$ is Hamiltonian, then its underlying simple graph is $(k+\ell-1)$-degenerate and thus the chromatic number of $D$ is at most $k+\ell$, which is tight., Comment: 16 pages, 6 figures

An $r$-dynamic $k$-coloring of a graph $G$ is a proper $k$-coloring such that for any vertex $v$, there are at least $\min\{r,\deg_G(v) \}$ distinct colors in $N_G(v)$. The $r$-dynamic chromatic number $\chi_r^d(G)$ of a graph $G$ is the least $k$ such that there exists an $r$-dynamic $k$-coloring of $G$. The {\em list $r$-dynamic chromatic number} of a graph $G$ is denoted by $ch_r^d(G)$. Recently, Loeb et al. [UI] showed that the list $3$-dynamic chromatic number of a planar graph is at most 10. And Cheng et al. [Lai-16] studied the maximum average condition to have $\chi_3^d (G) \leq 4, \ 5$, or $6$. On the other hand, Song et al. [SLW] showed that if $G$ is planar with girth at least 6, then $\chi_r^d(G)\le r+5$ for any $r\ge 3$. In this paper, we study list 3-dynamic coloring in terms of maximum average degree. We show that $ch^d_3(G) \leq 6$ if $mad(G) < \frac{18}{7}$, $ch^d_3(G) \leq 7$ if $mad(G) < \frac{14}{5}$, and $ch^d_3(G) \leq 8$ if $mad(G) < 3$. All of the bounds are tight., Comment: 18 pages

The square $G^2$ of a graph $G$ is the graph defined on $V(G)$ such that two vertices $u$ and $v$ are adjacent in $G^2$ if the distance between $u$ and $v$ in $G$ is at most 2. The {\em maximum average degree} of $G$, $mad (G)$, is the maximum among the average degrees of the subgraphs of $G$. It is known in \cite{BLP-14-JGT} that there is no constant $C$ such that every graph $G$ with $mad(G)< 4$ has $\chi(G^2) \leq \Delta(G) + C$. Charpentier \cite{Charpentier14} conjectured that there exists an integer $D$ such that every graph $G$ with $\Delta(G)\ge D$ and $mad(G)<4$ has $\chi(G^2) \leq 2 \Delta(G)$. Recent result in \cite{BLP-DM} implies that $\chi(G^2) \leq 2 \Delta(G)$ if $mad(G) < 4 -\frac{1}{c}$ with $\Delta(G) \geq 40c -16$. In this paper, we show for $c\ge 2$, if $mad(G) < 4 - \frac{1}{c}$ and $\Delta(G) \geq 14c-7$, then $\chi_\ell(G^2) \leq 2 \Delta(G)$, which improves the result in \cite{BLP-DM}. We also show that for every integer $D$, there is a graph $G$ with $\Delta(G)\ge D$ such that $mad(G)<4$, and $\chi(G^2) \geq 2\Delta(G) +2$, which disproves Charpentier's conjecture. In addition, we give counterexamples to Charpentier's another conjecture in \cite{Charpentier14}, stating that for every integer $k\ge 3$, there is an integer $D_k$ such that every graph $G$ with $mad(G)<2k$ and $\Delta(G)\ge D_k$ has $\chi(G^2) \leq k\Delta(G) -k$.

The {\em square} $G^2$ of a graph $G$ is the graph with the same vertex set as $G$ and with two vertices adjacent if their distance in $G$ is at most 2. Thomassen showed that every planar graph $G$ with maximum degree $\Delta(G)=3$ satisfies $\chi(G^2)\leq 7$. Kostochka and Woodall conjectured that for every graph, the list-chromatic number of $G^2$ equals the chromatic number of $G^2$, that is $\chi_l(G^2)=\chi(G^2)$ for all $G$. If true, this conjecture (together with Thomassen's result) implies that every planar graph $G$ with $\Delta(G)=3$ satisfies $\chi_l(G^2)\leq 7$. We prove that every connected graph (not necessarily planar) with $\Delta(G)=3$ other than the Petersen graph satisfies $\chi_l(G^2)\leq 8$ (and this is best possible). In addition, we show that if $G$ is a planar graph with $\Delta(G)=3$ and girth $g(G)\geq 7$, then $\chi_l(G^2)\leq 7$. Dvo\v{r}\'ak, \v{S}krekovski, and Tancer showed that if $G$ is a planar graph with $\Delta(G) = 3$ and girth $g(G) \geq 10$, then $\chi_l(G^2)\leq 6$. We improve the girth bound to show that if $G$ is a planar graph with $\Delta(G)=3$ and $g(G) \geq 9$, then $\chi_l(G^2) \leq 6$. All of our proofs can be easily translated into linear-time coloring algorithms., Comment: This is the accepted version of the journal paper referenced below, which has been published in final form at http://onlinelibrary.wiley.com/doi/10.1002/jgt.20273/abstract. The abstract incorrectly stated that Thomassen solved Wegner's Conjecture for $\Delta(G)=3$; however, all of our results are correct

For a loopless multigraph $G$, the fractional arboricity $Arb(G)$ is the maximum of $\frac{|E(H)|}{|V(H)|-1}$ over all subgraphs $H$ with at least two vertices. Generalizing the Nash-Williams Arboricity Theorem, the Nine Dragon Tree Conjecture asserts that if $Arb(G)\le k+\frac{d}{k+d+1}$, then $G$ decomposes into $k+1$ forests with one having maximum degree at most $d$. The conjecture was previously proved for $d=k+1$ and for $k=1$ when $d \le 6$. We prove it for all $d$ when $k \le 2$, except for $(k,d)=(2,1)$., Comment: 15 pages

The square $G^2$ of a graph $G$ is the graph defined on $V(G)$ such that two vertices $u$ and $v$ are adjacent in $G^2$ if the distance between $u$ and $v$ in $G$ is at most 2. Let $\chi(H)$ and $\chi_{\ell}(H)$ be the chromatic number and the list chromatic number of $H$, respectively. A graph $H$ is called {\em chromatic-choosable} if $\chi_{\ell} (H) = \chi(H)$. It is an interesting problem to find graphs that are chromatic-choosable. Motivated by the List Total Coloring Conjecture, Kostochka and Woodall (2001) proposed the List Square Coloring Conjecture which states that $G^2$ is chromatic-choosable for every graph $G$. Recently, Kim and Park showed that the List Square Coloring Conjecture does not hold in general by finding a family of graphs whose squares are complete multipartite graphs with partite sets of unbounded size. It is a well-known fact that the List Total Coloring Conjecture is true if the List Square Coloring Conjecture holds for special class of bipartite graphs. On the other hand, the counterexamples to the List Square Coloring Conjecture are not bipartite graphs. Hence a natural question is whether $G^2$ is chromatic-choosable or not for every bipartite graph $G$. In this paper, we give a bipartite graph $G$ such that $\chi_{\ell} (G^2) \neq \chi(G^2)$. Moreover, we show that the value $\chi_{\ell}(G^2) - \chi(G^2)$ can be arbitrarily large., Comment: 13 pages, 5 figures

The Kneser graph $K(n,k)$ is the graph whose vertices are the $k$-element subsets of an $n$ elements set, with two vertices adjacent if they are disjoint. The square $G^2$ of a graph $G$ is the graph defined on $V(G)$ such that two vertices $u$ and $v$ are adjacent in $G^2$ if the distance between $u$ and $v$ in $G$ is at most 2. Determining the chromatic number of the square of the Kneser graph $K(n, k)$ is an interesting graph coloring problem, and is also related with intersecting family problem. The square of $K(2k, k)$ is a perfect matching and the square of $K(n, k)$ is the complete graph when $n \geq 3k-1$. Hence coloring of the square of $K(2k +1, k)$ has been studied as the first nontrivial case. In this paper, we focus on the question of determining $\chi(K^2(2k+r,k))$ for $r \geq 2$. Recently, Kim and Park \cite{KP2014} showed that $\chi(K^2(2k+1,k)) \leq 2k+2$ if $ 2k +1 = 2^t -1$ for some positive integer $t$. In this paper, we generalize the result by showing that for any integer $r$ with $1 \leq r \leq k -2$, (a) $\chi(K^2 (2k+r, k)) \leq (2k+r)^r$, if $2k + r = 2^t$ for some integer $t$, and (b) $\chi(K^2 (2k+r, k)) \leq (2k+r+1)^r$, if $2k + r = 2^t-1$ for some integer $t$. On the other hand, it was showed in \cite{KP2014} that $\chi(K^2 (2k+r, k)) \leq (r+2)(3k + \frac{3r+3}{2})^r$ for $2 \leq r \leq k-2$. We improve these bounds by showing that for any integer $r$ with $2 \leq r \leq k -2$, we have $\chi(K^2 (2k+r, k)) \leq2 \left(\frac{9}{4}k + \frac{9(r+3)}{8} \right)^r$. Our approach is also related with injective coloring and coloring of Johnson graph.

The $k$th power $G^k$ of a graph $G$ is the graph defined on $V(G)$ such that two vertices $u$ and $v$ are adjacent in $G^k$ if the distance between $u$ and $v$ in $G$ is at most $k$. Let $\chi(H)$ and $\chi_l(H)$ be the chromatic number and the list chromatic number of $H$, respectively. A graph $H$ is called {\em chromatic-choosable} if $\chi_l (H) = \chi(H)$. It is an interesting problem to find graphs that are chromatic-choosable. A natural question raised by Xuding Zhu (2012) is whether there exists a constant integer $k$ such that $G^k$ is chromatic-choosable for every graph $G$. Motivated by the List Total Coloring Conjecture, Kostochka and Woodall (2001) asked whether $G^2$ is chromatic-choosable for every graph $G$. Kim and Park (2013) answered the Kostochka and Woodall's question in the negative by finding a family of graphs whose squares are complete multipartite graphs with partite sets of equal and unbounded size. In this paper, we answer Zhu's question by showing that for every integer $k \geq 2$, there exists a graph $G$ such that $G^k$ is not chromatic-choosable. Moreover, for any fixed $k$ we show that the value $\chi_l(G^k) - \chi(G^k)$ can be arbitrarily large., Comment: 11 pages