On the vertex-arboricity of planar graphs without 7-cycles

The vertex arboricity $va\left(G\right)$ of a graph $G$ is the minimum number of colors the vertices can be labeled so that each color class induces a forest. It was well-known that $va\left(G\right)\le 3$ for every planar graph $G$. In this paper, we prove that $va\left(G\right)\le 2$ if $G$ is a planar graph without 7-cycles. This extends a result in [A. Raspaud, W. Wang, On the vertex-arboricity of planar graphs, European J. Combin. 29 (2008) 1064–1075] that for each $k\in \{3,4,5,6\}$, planar graphs $G$ without $k$-cycles have $va\left(G\right)\le 2$.     

List 3-dynamic coloring of graphs with small maximum average degree

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\left(v\right)\}$ distinct colors in $N_G\left(v\right)$. The $r$-dynamic chromatic number${\chi }_r^d\left(G\right)$ 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 $c{h}_r^d\left(G\right)$.Recently, Loeb et al. (0000) showed that the list $3$-dynamic chromatic number of a planar graph is at most 10. And Cheng et al. (0000) studied the maximum average condition to have ${\chi }_3^d\left(G\right)\le 4,5$, or $6$. On the other hand, Song et al. (2016) showed that if $G$ is planar with girth at least 6, then ${\chi }_r^d\left(G\right)\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 $c{h}_3^d\left(G\right)\le 6$ if $mad\left(G\right)<\frac{18}{7}$, $c{h}_3^d\left(G\right)\le 7$ if $mad\left(G\right)<\frac{14}{5}$, and $c{h}_3^d\left(G\right)\le 8$ if $mad\left(G\right)<3$. All of the bounds are tight.     

Structure and algorithms for (cap,even hole)-free graphs

A graph is even-hole-free if it has no induced even cycles of length 4 or more. A cap is a cycle of length at least 5 with exactly one chord and that chord creates a triangle with the cycle. In this paper, we consider (cap, even hole)-free graphs, and more generally, (cap, 4-hole)-free odd-signable graphs. We give an explicit construction of these graphs. We prove that every such graph $G$ has a vertex of degree at most $\frac{3}{2}\omega \left(G\right)?1$, and hence $\chi \left(G\right)\le \frac{3}{2}\omega \left(G\right)$, where $\omega \left(G\right)$ denotes the size of a largest clique in $G$ and $\chi \left(G\right)$ denotes the chromatic number of $G$. We give an $O\left(nm\right)$ algorithm for $q$-coloring these graphs for fixed $q$ and an $O\left(nm\right)$ algorithm for maximum weight stable set, where $n$ is the number of vertices and $m$ is the number of edges of the input graph. We also give a polynomial-time algorithm for minimum coloring.Our algorithms are based on our results that triangle-free odd-signable graphs have treewidth at most 5 and thus have clique-width at most 48, and that (cap, 4-hole)-free odd-signable graphs $G$ without clique cutsets have treewidth at most $6\omega \left(G\right)?1$ and clique-width at most 48.     

An improved upper bound on the adjacent vertex distinguishing total chromatic number of graphs

An adjacent vertex distinguishing total $k$-coloring of a graph $G$ is a proper total $k$-coloring of $G$ such that any pair of adjacent vertices have different sets of colors. The minimum number $k$ needed for such a total coloring of $G$ is denoted by ${\chi }_a^{\prime \prime }\left(G\right)$. In this paper we prove that ${\chi }_a^{\prime \prime }\left(G\right)\le 2\Delta \left(G\right)?1$ if $\Delta \left(G\right)\ge 4$, and ${\chi }_a^{\prime \prime }\left(G\right)\le ?\frac{5\Delta \left(G\right)+8}{3}?$ in general. This improves a result in Huang et al. (2012) which states that ${\chi }_a^{\prime \prime }\left(G\right)\le 2\Delta \left(G\right)$ for any graph with $\Delta \left(G\right)\ge 3$.     

A characterization for the neighbor-distinguishing total chromatic number of planar graphs with Δ=13

The neighbor-distinguishing total chromatic number ${\chi }_a^{\prime \prime }\left(G\right)$ of a graph $G$ is the smallest integer $k$ such that $G$ can be totally colored using $k$ colors with a condition that any two adjacent vertices have different sets of colors. In this paper, we give a sufficient and necessary condition for a planar graph $G$ with maximum degree 13 to have ${\chi }_a^{\prime \prime }\left(G\right)=14$ or ${\chi }_a^{\prime \prime }\left(G\right)=15$. Precisely, we show that if $G$ is a planar graph of maximum degree 13, then $14\le {\chi }_a^{\prime \prime }\left(G\right)\le 15$; and ${\chi }_a^{\prime \prime }\left(G\right)=15$ if and only if $G$ contains two adjacent 13-vertices.     

On 3-stable number conditions in n-connected claw-free graphs

For a subgraph $X$ of $G$, let ${\alpha }_G^3\left(X\right)$ be the maximum number of vertices of $X$ that are pairwise distance at least three in $G$. In this paper, we prove three theorems. Let $n$ be a positive integer, and let $H$ be a subgraph of an $n$-connected claw-free graph $G$. We prove that if $n\ge 2$, then either $H$ can be covered by a cycle in $G$, or there exists a cycle $C$ in $G$ such that ${\alpha }_G^3(H?V\left(C\right))\le {\alpha }_G^3\left(H\right)?n$. This result generalizes the result of Broersma and Lu that $G$ has a cycle covering all the vertices of $H$ if ${\alpha }_G^3\left(H\right)\le n$. We also prove that if $n\ge 1$, then either $H$ can be covered by a path in $G$, or there exists a path $P$ in $G$ such that ${\alpha }_G^3(H?V\left(P\right))\le {\alpha }_G^3\left(H\right)?n?1$. By using the second result, we prove the third result. For a tree $T$, a vertex of $T$ with degree one is called a leaf of $T$. For an integer $k\ge 2$, a tree which has at most $k$ leaves is called a $k$-ended tree. We prove that if ${\alpha }_G^3\left(H\right)\le n+k?1$, then $G$ has a $k$-ended tree covering all the vertices of $H$. This result gives a positive answer to the conjecture proposed by Kano et al. (2012).     

On disjoint matchings in cubic graphs

For $i=2,3$ and a cubic graph $G$ let ${\nu }_i\left(G\right)$ denote the maximum number of edges that can be covered by $i$ matchings. We show that ${\nu }_2\left(G\right)\ge \frac{4}{5}\left|V\left(G\right)\right|$ and ${\nu }_3\left(G\right)\ge \frac{7}{6}\left|V\left(G\right)\right|$. Moreover, it turns out that ${\nu }_2\left(G\right)\le \frac{\left|V\left(G\right)\right|+2{\nu }_3\left(G\right)}{4}$.     

List star chromatic index of sparse graphs

A star edge-coloring of a graph $G$ is a proper edge coloring such that every 2-colored connected subgraph of $G$ is a path of length at most 3. For a graph $G$, let the list star chromatic index of $G$, $c{h}_s^{\prime }\left(G\right)$, be the minimum $k$ such that for any $k$-uniform list assignment $L$ for the set of edges, $G$ has a star edge-coloring from $L$. Dvo?ák et al. (2013) asked whether the list star chromatic index of every subcubic graph is at most 7. In Kerdjoudj et al. (2017) we proved that it is at most 8. In this paper we consider graphs with any maximum degree, we proved that if the maximum average degree of a graph $G$ is less than $\frac{14}{5}$ (resp. 3), then $c{h}_s^{\prime }\left(G\right)\le 2\Delta \left(G\right)+2$ (resp. $c{h}_s^{\prime }\left(G\right)\le 2\Delta \left(G\right)+3$).     

Edge-partitions of graphs and their neighbor-distinguishing index

A proper edge coloring is neighbor-distinguishing if any two adjacent vertices have distinct sets consisting of colors of their incident edges. The minimum number of colors needed for a neighbor-distinguishing edge coloring is the neighbor-distinguishing index, denoted by ${\chi }_a^{\prime }\left(G\right)$. A graph is normal if it contains no isolated edges. Let $G$ be a normal graph, and let $\Delta \left(G\right)$ and ${\chi }^{\prime }\left(G\right)$ denote the maximum degree and the chromatic index of $G$, respectively. We modify the previously known techniques of edge-partitioning to prove that ${\chi }_a^{\prime }\left(G\right)\le 2{\chi }^{\prime }\left(G\right)$, which implies that ${\chi }_a^{\prime }\left(G\right)\le 2\Delta \left(G\right)+2$. This improves the result in Wang et al. (2015), which states that ${\chi }_a^{\prime }\left(G\right)\le \frac{5}{2}\Delta \left(G\right)$ for any normal graph. We also prove that ${\chi }_a^{\prime }\left(G\right)\le 2\Delta \left(G\right)$ when $\Delta \left(G\right)=2^k$, $k$ is an integer with $k\ge 2$.