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.     

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.     

A note on the list vertex arboricity of toroidal graphs

The vertex arboricity $a\left(G\right)$ of a graph $G$ is the minimum number of colors required to color the vertices of $G$ such that no cycle is monochromatic. The list vertex arboricity $a_l\left(G\right)$ is the list-coloring version of this concept. In this note, we prove that if $G$ is a toroidal graph, then $a_l\left(G\right)\le 4$; and $a_l\left(G\right)=4$ if and only if $G$ contains $K_7$ as an induced subgraph.     

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 note on planar graphs with large width parameters and small grid-minors

Given a graph $G$ with tree-width $\omega \left(G\right)$, branch-width $\beta \left(G\right)$, and side size of the largest square grid-minor $\theta \left(G\right)$, it is known that $\theta \left(G\right)\le \beta \left(G\right)\le \omega \left(G\right)+1\le \frac{3}{2}\beta \left(G\right)$. In this paper, we introduce another approach to bound the side size of the largest square grid-minor specifically for planar graphs. The approach is based on measuring the distances between the faces in an embedding of a planar graph. We analyze the tightness of all derived bounds. In particular, we present a class of planar graphs where $\theta \left(G\right)=\beta \left(G\right)<\omega \left(G\right)=?\frac{3}{2}\theta \left(G\right)??1$.     

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

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

A degree condition for a graph to have (a,b)-parity factors

Let $a$ and $b$ be two positive integers such that $a\le b$ and $a\equiv b(mod2)$. A graph $F$ is an $(a,b)$-parity factor of a graph $G$ if $F$ is a spanning subgraph of $G$ and for all vertices $v\in V\left(F\right)$, $d_F\left(v\right)\equiv b(mod2)$ and $a\le d_F\left(v\right)\le b$. In this paper we prove that every connected graph $G$ with $n\ge b(a+b)(a+b+2)∕\left(2a\right)$ vertices has an $(a,b)$-parity factor if $na$ is even, $\delta \left(G\right)\ge (b?a)∕a+a$, and for any two nonadjacent vertices $u,v\in V\left(G\right)$, $max\{d_G\left(u\right),d_G\left(v\right)\}\ge \frac{an}{a+b}$. This extends an earlier result of Nishimura (1992) and strengthens a result of Cai and Li (1998).     

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

The list L(2,1)-labeling of planar graphs

Let $\mathbf{N}$ be the set of all positive integers. A list assignment of a graph $G$ is a function $L:V\left(G\right)?2^{\mathbf{N}}$ that assigns each vertex $v$ a list $L\left(v\right)$ for all $v\in V\left(G\right)$. We say that $G$ is $L$-$(2,1)$-choosable if there exists a function $?$ such that $?\left(v\right)\in L\left(v\right)$ for all $v\in V\left(G\right)$, $|?\left(u\right)??\left(v\right)|\ge 2$ if $u$ and $v$ are adjacent, and $|?\left(u\right)??\left(v\right)|\ge 1$ if $u$ and $v$ are at distance 2. The list-$L(2,1)$-labeling number ${\lambda }_l\left(G\right)$ of $G$ is the minimum $k$ such that for every list assignment $L=\{L\left(v\right):|L\left(v\right)|=k,v\in V\left(G\right)\}$, $G$ is $L$-$(2,1)$-choosable. We prove that if $G$ is a planar graph with girth $g\ge 8$ and its maximum degree $\Delta$ is large enough, then ${\lambda }_l\left(G\right)\le \Delta +3$. There are graphs with large enough $\Delta$ and $g\ge 8$ having ${\lambda }_l\left(G\right)=\Delta +3$.     

Properties of minimally t-tough graphs

A graph $G$ is minimally $t$-tough if the toughness of $G$ is $t$ and the deletion of any edge from $G$ decreases the toughness. Kriesell conjectured that for every minimally $1$-tough graph the minimum degree $\delta \left(G\right)=2$. We show that in every minimally $1$-tough graph $\delta \left(G\right)\le \frac{n}{3}+1$. We also prove that every minimally $1$-tough, claw-free graph is a cycle. On the other hand, we show that for every positive rational number $t$ any graph can be embedded as an induced subgraph into a minimally $t$-tough graph.     

Distant total irregularity strength of graphs via random vertex ordering

Let $c:V\cup E\to \{1,2,\dots ,k\}$ be a (not necessarily proper) total colouring of a graph $G=(V,E)$ with maximum degree $\Delta$. Two vertices $u,v\in V$ are sum distinguished if they differ with respect to sums of their incident colours, i.e. $c\left(u\right)+{\sum }_{e?u}c\left(e\right)\ne c\left(v\right)+{\sum }_{e?v}c\left(e\right)$. The least integer $k$ admitting such colouring $c$ under which every $u,v\in V$ at distance $1\le d(u,v)\le r$ in $G$ are sum distinguished is denoted by ${\mathrm{ts}}_r\left(G\right)$. Such graph invariants link the concept of the total vertex irregularity strength of graphs with so-called 1-2-Conjecture, whose concern is the case of $r=1$. Within this paper we combine probabilistic approach with purely combinatorial one in order to prove that ${\mathrm{ts}}_r\left(G\right)\le (2+o\left(1\right)){\Delta }^{r?1}$ for every integer $r\ge 2$ and each graph $G$, thus improving the previously best result: ${\mathrm{ts}}_r\left(G\right)\le 3{\Delta }^{r?1}$.