Adjacent vertex distinguishing total colorings of outerplanar graphs

An adjacent vertex distinguishing total coloring of a graph G is a proper total coloring of G such that any pair of adjacent vertices are incident to distinct sets of colors. The minimum number of colors required for an adjacent vertex distinguishing total coloring of G is denoted by χ″ _a (G). In this paper, we characterize completely the adjacent vertex distinguishing total chromatic number of outerplanar graphs.     

Adjacent vertex distinguishing edge coloring of IC-planar graphs

Journal of Combinatorial Optimization - The adjacent vertex distinguishing edge coloring of a graph G is a proper edge coloring in which each pair of adjacent vertices is assigned different color...     

Adjacent vertex distinguishing edge-colorings of graphs with smaller maximum average degree

An adjacent vertex distinguishing edge-coloring of a graph G is a proper edge coloring of G such that any pair of adjacent vertices are incident to distinct sets of colors. The minimum number of colors required for an adjacent vertex distinguishing edge-coloring of G is denoted by χ′ _a (G). Let mad(G)\mathop{\mathrm{mad}}(G) and Δ denote the maximum average degree and the maximum degree of a graph G, respectively.     

The adjacent vertex distinguishing total coloring of planar graphs

An adjacent vertex distinguishing total coloring of a graph G is a proper total coloring of G such that any pair of adjacent vertices have distinct sets of colors. The minimum number of colors needed for an adjacent vertex distinguishing total coloring of G is denoted by $\chi''_{a}(G)$ . In this paper, we characterize completely the adjacent vertex distinguishing total chromatic number of planar graphs G with large maximum degree Δ by showing that if Δ≥14, then $\varDelta+1\leq \chi''_{a}(G)\leq \varDelta+2$ , and $\chi''_{a}(G)=\varDelta+2$ if and only if G contains two adjacent vertices of maximum degree.     

Sharp upper bound of injective coloring of planar graphs with girth at least 5

Journal of Combinatorial Optimization - An injective k-coloring of a graph G is a k-coloring c (not necessarily proper) such that $$c(u)\ne c(v)$$ whenever u, v has a common neighbor in G. The...     

2-Distance coloring of planar graphs with girth 5

A vertex coloring is said to be 2-distance if any two distinct vertices of distance at most 2 receive different colors. Let G be a planar graph with girth at least 5. In this paper, we prove that G admits a 2-distance coloring with at most \(\Delta (G)+3\) colors if \(\Delta (G)\ge 339\).     

The adjacent vertex distinguishing total chromatic numbers of planar graphs with $$\Delta =10$$

A (proper) total-k-coloring of a graph G is a mapping \(\phi : V (G) \cup E(G)\mapsto \{1, 2, \ldots , k\}\) such that any two adjacent elements in \(V (G) \cup E(G)\) receive different colors. Let C(v) denote the set of the color of a vertex v and the colors of all incident edges of v. A total-k-adjacent vertex distinguishing-coloring of G is a total-k-coloring of G such that for each edge \(uv\in E(G)\), \(C(u)\ne C(v)\). We denote the smallest value k in such a coloring of G by \(\chi ''_{a}(G)\). It is known that \(\chi _{a}''(G)\le \Delta (G)+3\) for any planar graph with \(\Delta (G)\ge 11\). In this paper, we show that if G is a planar graph with \(\Delta (G)\ge 10\), then \(\chi _{a}''(G)\le \Delta (G)+3\). Our approach is based on Combinatorial Nullstellensatz and the discharging method.     

A lower bound of the surviving rate of a planar graph with girth at least seven

Let G be a connected graph with n≥2 vertices. Suppose that a fire breaks out at a vertex v of G. A firefighter starts to protect vertices. At each time interval, the firefighter protects one vertex not yet on fire. At the end of each time interval, the fire spreads to all the unprotected vertices that have a neighbor on fire. Let sn(v) denote the maximum number of vertices in G that the firefighter can save when a fire breaks out at vertex v. The surviving rate ρ(G) of G is defined to be ∑ _v∈V(G)sn(v)/n ², which is the average proportion of saved vertices. In this paper, we show that if G is a planar graph with n≥2 vertices and having girth at least 7, then $\rho(G)>\frac{1}{301}$ .     

Neighbor sum distinguishing total choosability of planar graphs

A total-k-coloring of a graph G is a mapping \(c: V(G)\cup E(G)\rightarrow \{1, 2,\dots , k\}\) such that any two adjacent or incident elements in \(V(G)\cup E(G)\) receive different colors. For a total-k-coloring of G, let \(\sum _c(v)\) denote the total sum of colors of the edges incident with v and the color of v. If for each edge \(uv\in E(G)\), \(\sum _c(u)\ne \sum _c(v)\), then we call such a total-k-coloring neighbor sum distinguishing. The least number k needed for such a coloring of G is the neighbor sum distinguishing total chromatic number, denoted by \(\chi _{\Sigma }^{''}(G)\). Pil?niak and Wo?niak conjectured \(\chi _{\Sigma }^{''}(G)\le \Delta (G)+3\) for any simple graph with maximum degree \(\Delta (G)\). In this paper, we prove that for any planar graph G with maximum degree \(\Delta (G)\), \(ch^{''}_{\Sigma }(G)\le \max \{\Delta (G)+3,16\}\), where \(ch^{''}_{\Sigma }(G)\) is the neighbor sum distinguishing total choosability of G.     

The effect of vertex and edge deletion on the edge metric dimension of graphs

Journal of Combinatorial Optimization - Let $$G=(V(G),E(G))$$ be a connected graph. A set of vertices $$S\subseteq V(G)$$ is an edge metric generator of G if any pair of edges in G can be...     

Neighbor sum distinguishing total coloring of planar graphs without 4-cycles

Let \(G=(V,E)\) be a graph and \(\phi : V\cup E\rightarrow \{1,2,\ldots ,k\}\) be a proper total coloring of G. Let f(v) denote the sum of the color on a vertex v and the colors on all the edges incident with v. The coloring \(\phi \) is neighbor sum distinguishing if \(f(u)\ne f(v)\) for each edge \(uv\in E(G)\). The smallest integer k in such a coloring of G is the neighbor sum distinguishing total chromatic number of G, denoted by \(\chi _{\Sigma }''(G)\). Pil?niak and Wo?niak conjectured that \(\chi _{\Sigma }''(G)\le \Delta (G)+3\) for any simple graph. By using the famous Combinatorial Nullstellensatz, we prove that \(\chi _{\Sigma }''(G)\le \max \{\Delta (G)+2, 10\}\) for planar graph G without 4-cycles. The bound \(\Delta (G)+2\) is sharp if \(\Delta (G)\ge 8\).     

Acyclic edge coloring of planar graphs without 4-cycles

An acyclic edge coloring of a graph G is a proper edge coloring such that no bichromatic cycles are produced. The acyclic chromatic index a′(G) of G is the smallest integer k such that G has an acyclic edge coloring using k colors. Fiam?ik (Math. Slovaca 28:139–145, 1978) and later Alon, Sudakov and Zaks (J. Graph Theory 37:157–167, 2001) conjectured that a′(G)≤Δ+2 for any simple graph G with maximum degree Δ. In this paper, we confirm this conjecture for planar graphs G with Δ≠4 and without 4-cycles.     

List edge and list total coloring of planar graphs with maximum degree 8

Let \(G\) be a planar graph with maximum degree \(\varDelta \ge 8\) and without chordal 5-cycles. Then \(\chi '_{l}(G)=\varDelta \) and \(\chi ''_{l}(G)=\varDelta +1\).     

Acyclic coloring of graphs with some girth restriction

A vertex coloring of a graph \(G\) is called acyclic if it is a proper vertex coloring such that every cycle \(C\) receives at least three colors. The acyclic chromatic number of \(G\) is the least number of colors in an acyclic coloring of \(G\). We prove that acyclic chromatic number of any graph \(G\) with maximum degree \(\Delta \ge 4\) and with girth at least \(4\Delta \) is at most \(12\Delta \).     

A proper total coloring distinguishing adjacent vertices by sums of planar graphs without intersecting triangles

Let \(G=(V,E)\) be a graph and \(\phi \) be a total \(k\)-coloring of \(G\) using the color set \(\{1,\ldots , k\}\). Let \(\sum _\phi (u)\) denote the sum of the color of the vertex \(u\) and the colors of all incident edges of \(u\). A \(k\)-neighbor sum distinguishing total coloring of \(G\) is a total \(k\)-coloring of \(G\) such that for each edge \(uv\in E(G)\), \(\sum _\phi (u)\ne \sum _\phi (v)\). By \(\chi ^{''}_{nsd}(G)\), we denote the smallest value \(k\) in such a coloring of \(G\). Pil?niak and Wo?niak first introduced this coloring and conjectured that \(\chi _{nsd}^{''}(G)\le \Delta (G)+3\) for any simple graph \(G\). In this paper, we prove that the conjecture holds for planar graphs without intersecting triangles with \(\Delta (G)\ge 7\). Moreover, we also show that \(\chi _{nsd}^{''}(G)\le \Delta (G)+2\) for planar graphs without intersecting triangles with \(\Delta (G) \ge 9\). Our approach is based on the Combinatorial Nullstellensatz and the discharging method.     

First-Fit colorings of graphs with no cycles of a prescribed even length

The First-Fit (or Grundy) chromatic number of a graph G denoted by \(\chi _{{_\mathsf{FF}}}(G)\), is the maximum number of colors used by the First-Fit (greedy) coloring algorithm when applied to G. In this paper we first show that any graph G contains a bipartite subgraph of Grundy number \(\lfloor \chi _{{_\mathsf{FF}}}(G) /2 \rfloor +1\). Using this result we prove that for every \(t\ge 2\) there exists a real number \(c>0\) such that in every graph G on n vertices and without cycles of length 2t, any First-Fit coloring of G uses at most \(cn^{1/t}\) colors. It is noted that for \(t=2\) this bound is the best possible. A compactness conjecture is also proposed concerning the First-Fit chromatic number involving the even girth of graphs.     

Equitable vertex arboricity of 5-degenerate graphs

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.     

Acyclic edge coloring of planar graphs without a 3-cycle adjacent to a 6-cycle

An acyclic edge coloring of a graph \(G\) is a proper edge coloring such that no bichromatic cycles are produced. The acyclic chromatic index \(a'(G)\) of \(G\) is the smallest integer \(k\) such that \(G\) has an acyclic edge coloring using \(k\) colors. Fiam? ik (Math Slovaca 28:139–145, 1978) and later Alon et al. (J Graph Theory 37:157–167, 2001) conjectured that \(a'(G)\le \Delta +2\) for any simple graph \(G\) with maximum degree \(\Delta \) . In this paper, we confirm this conjecture for planar graphs without a \(3\) -cycle adjacent to a \(6\) -cycle.