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$.     

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.     

3-dynamic coloring of planar triangulations

An $r$-dynamic $k$-coloring of a graph $G$ is a proper $k$-coloring such that any vertex $v$ has 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$.Loeb et al. (2018) showed that if $G$ is a planar graph, then ${\chi }_3^d\left(G\right)\le 10$, and there is a planar graph $G$ with ${\chi }_3^d\left(G\right)=7$. Thus, finding an optimal upper bound on ${\chi }_3^d\left(G\right)$ for a planar graph $G$ is a natural interesting problem. In this paper, we show that ${\chi }_3^d\left(G\right)\le 5$ if $G$ is a planar triangulation. The upper bound is sharp.     

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$.     

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$.     

Maximum matchings in regular graphs

It was conjectured by Mkrtchyan, Petrosyan and Vardanyan that every graph $G$ with $\Delta \left(G\right)?\delta \left(G\right)\le 1$ has a maximum matching $M$ such that any two $M$-unsaturated vertices do not share a neighbor. The results obtained in Mkrtchyan et al. (2010), Petrosyan (2014) and Picouleau (2010) leave the conjecture unknown only for $k$-regular graphs with $4\le k\le 6$. All counterexamples for $k$-regular graphs $(k\ge 7)$ given in Petrosyan (2014) have multiple edges. In this paper, we confirm the conjecture for all $k$-regular simple graphs and also $k$-regular multigraphs with $k\le 4$.     

Equitable defective coloring of sparse planar graphs

A graph has an equitable, defective $k$-coloring (an ED-$k$-coloring) if there is a $k$-coloring of $V\left(G\right)$ that is defective (every vertex shares the same color with at most one neighbor) and equitable (the sizes of all color classes differ by at most one). A graph may have an ED-$k$-coloring, but no ED-$(k+1)$-coloring. In this paper, we prove that planar graphs with minimum degree at least $2$ and girth at least $10$ are ED-$k$-colorable for any integer $k\ge 3$. The proof uses the method of discharging. We are able to simplify the normally lengthy task of enumerating forbidden substructures by using Hall’s Theorem, an unusual approach.     

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.     

Some bounds on the number of colors in interval and cyclic interval edge colorings of graphs

An interval$t$-coloring of a multigraph $G$ is a proper edge coloring with colors $1,\dots ,t$ such that the colors of the edges incident with every vertex of $G$ are colored by consecutive colors. A cyclic interval$t$-coloring of a multigraph $G$ is a proper edge coloring with colors $1,\dots ,t$ such that the colors of the edges incident with every vertex of $G$ are colored by consecutive colors, under the condition that color $1$ is considered as consecutive to color $t$. Denote by $w\left(G\right)$ ($w_c\left(G\right)$) and $W\left(G\right)$ ($W_c\left(G\right)$) the minimum and maximum number of colors in a (cyclic) interval coloring of a multigraph $G$, respectively. We present some new sharp bounds on $w\left(G\right)$ and $W\left(G\right)$ for multigraphs $G$ satisfying various conditions. In particular, we show that if $G$ is a $2$-connected multigraph with an interval coloring, then $W\left(G\right)\le 1+?\frac{\left|V\left(G\right)\right|}{2}?(\Delta \left(G\right)?1)$. We also give several results towards the general conjecture that $W_c\left(G\right)\le \left|V\left(G\right)\right|$ for any triangle-free graph $G$ with a cyclic interval coloring; we establish that approximate versions of this conjecture hold for several families of graphs, and we prove that the conjecture is true for graphs with maximum degree at most $4$.     

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).     

A degree sum condition for graphs to be covered by two cycles

Let $G$ be a $k$-connected graph of order $n$. In [1], Bondy (1980) considered a degree sum condition for a graph to have a Hamiltonian cycle, say, to be covered by one cycle. He proved that if ${\sigma }_{k+1}\left(G\right)>(k+1)(n?1)/2$, then $G$ has a Hamiltonian cycle. On the other hand, concerning a degree sum condition for a graph to be covered by two cycles, Enomoto et al. (1995) [4] proved that if $k=1$ and ${\sigma }_3\left(G\right)\ge n$, then $G$ can be covered by two cycles. By these results, we conjecture that if ${\sigma }_{2k+1}\left(G\right)>(2k+1)(n?1)/3$, then $G$ can be covered by two cycles. In this paper, we prove the case $k=2$ of this conjecture. In fact, we prove a stronger result; if $G$ is 2-connected with ${\sigma }_5\left(G\right)\ge 5(n?1)/3$, then $G$ can be covered by two cycles, or $G$ belongs to an exceptional class.     

A sharp lower bound on Steiner Wiener index for trees with given diameter

Let $G$ be a connected graph with vertex set $V\left(G\right)$ and edge set $E\left(G\right)$. For a subset $S$ of $V\left(G\right)$, the Steiner distance$d\left(S\right)$ of $S$ is the minimum size of a connected subgraph whose vertex set contains $S$. For an integer $k$ with $2\le k\le n?1$, the Steiner$k$-Wiener index${\text{SW}}_k\left(G\right)$ is ${\sum }_{S?V\left(G\right),\left|S\right|=k}d\left(S\right)$. In this paper, we introduce some transformations for trees that do not increase their Steiner $k$-Wiener index for $2\le k\le n?1$. Using these transformations, we get a sharp lower bound on Steiner $k$-Wiener index for trees with given diameter, and obtain the corresponding extremal graph as well.     

Defective 2-colorings of planar graphs without 4-cycles and 5-cycles

A 2-coloring is a coloring of vertices of a graph with colors 1 and 2. Define $V_i?\{v\in V\left(G\right):c\left(v\right)=i\}$ for $i=1$ and $2.$ We say that $G$ is $(d_1,d_2)$-colorable if $G$ has a 2-coloring such that $V_i$ is an empty set or the induced subgraph $G\left[V_i\right]$ has the maximum degree at most $d_i$ for $i=1$ and $2.$ Let $G$ be a planar graph without 4-cycles and 5-cycles. We show that the problem to determine whether $G$ is $(0,k)$-colorable is NP-complete for every positive integer $k.$ Moreover, we construct non-$(1,k)$-colorable planar graphs without 4-cycles and 5-cycles for every positive integer $k.$ In contrast, we prove that $G$ is $(d_1,d_2)$-colorable where $(d_1,d_2)=(4,4),(3,5),$ and $(2,9).$     

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$).     

List r-hued chromatic number of graphs with bounded maximum average degrees

For integers $k,r>0$, a $(k,r)$-coloring of a graph $G$ is a proper coloring $c$ with at most $k$ colors such that for any vertex $v$ with degree $d\left(v\right)$, there are at least min$\{d\left(v\right),r\}$ different colors present at the neighborhood of $v$. The $r$-hued chromatic number of $G$, ${\chi }_r\left(G\right)$, is the least integer $k$ such that a $(k,r)$-coloring of $G$ exists. The list$r$-hued chromatic number${\chi }_{L,r}\left(G\right)$ of $G$ is similarly defined. Thus if $\Delta \left(G\right)\ge r$, then ${\chi }_{L,r}\left(G\right)\ge {\chi }_r\left(G\right)\ge r+1$. We present examples to show that, for any sufficiently large integer $r$, there exist graphs with maximum average degree less than 3 that cannot be $(r+1,r)$-colored. We prove that, for any fraction $q<\frac{14}{5}$, there exists an integer $R=R\left(q\right)$ such that for each $r\ge R$, every graph $G$ with maximum average degree $q$ is list $(r+1,r)$-colorable. We present examples to show that for some $r$ there exist graphs with maximum average degree less than 4 that cannot be $r$-hued colored with less than $\frac{3r}{2}$ colors. We prove that, for any sufficiently small real number $?>0$, there exists an integer $h=h\left(?\right)$ such that every graph $G$ with maximum average degree $4??$ satisfies ${\chi }_{L,r}\left(G\right)\le r+h\left(?\right)$. These results extend former results in Bonamy et al. (2014).