List 2-distance $$\varDelta +3$$-coloring of planar graphs without 4,5-cycles

Let \(\chi _2(G)\) and \(\chi _2^l(G)\) be the 2-distance chromatic number and list 2-distance chromatic number of a graph G, respectively. Wegner conjectured that for each planar graph G with maximum degree \(\varDelta \) at least 4, \(\chi _2(G)\le \varDelta +5\) if \(4\le \varDelta \le 7\), and \(\chi _2(G)\le \lfloor \frac{3\varDelta }{2}\rfloor +1\) if \(\varDelta \ge 8\). Let G be a planar graph without 4,5-cycles. We show that if \(\varDelta \ge 26\), then \(\chi _2^l(G)\le \varDelta +3\). There exist planar graphs G with girth \(g(G)=6\) such that \(\chi _2^l(G)=\varDelta +2\) for arbitrarily large \(\varDelta \). In addition, we also discuss the list L(2, 1)-labeling number of G, and prove that \(\lambda _l(G)\le \varDelta +8\) for \(\varDelta \ge 27\).     

More bounds for the Grundy number of graphs

A coloring of a graph \(G=(V,E)\) is a partition \(\{V_1, V_2, \ldots , V_k\}\) of V into independent sets or color classes. A vertex \(v\in V_i\) is a Grundy vertex if it is adjacent to at least one vertex in each color class \(V_j\) for every \(j<i\). A coloring is a Grundy coloring if every vertex is a Grundy vertex, and the Grundy number \(\Gamma (G)\) of a graph G is the maximum number of colors in a Grundy coloring. We provide two new upper bounds on Grundy number of a graph and a stronger version of the well-known Nordhaus-Gaddum theorem. In addition, we give a new characterization for a \(\{P_{4}, C_4\}\)-free graph by supporting a conjecture of Zaker, which says that \(\Gamma (G)\ge \delta (G)+1\) for any \(C_4\)-free graph G.     

On list <Emphasis Type="Italic">r</Emphasis>-hued coloring of planar graphs

A list assignment of G is a function L that assigns to each vertex \(v\in V(G)\) a list L(v) of available colors. Let r be a positive integer. For a given list assignment L of G, an (L, r)-coloring of G is a proper coloring \(\phi \) such that for any vertex v with degree d(v), \(\phi (v)\in L(v)\) and v is adjacent to at least \( min\{d(v),r\}\) different colors. The list r-hued chromatic number of G, \(\chi _{L,r}(G)\), is the least integer k such that for every list assignment L with \(|L(v)|=k\), \(v\in V(G)\), G has an (L, r)-coloring. We show that if \(r\ge 32\) and G is a planar graph without 4-cycles, then \(\chi _{L,r}(G)\le r+8\). This result implies that for a planar graph with maximum degree \(\varDelta \ge 26\) and without 4-cycles, Wagner’s conjecture in [Graphs with given diameter and coloring problem, Technical Report, University of Dortmund, Germany, 1977] holds.     

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

The game chromatic index of some trees with maximum degree four and adjacent degree-four vertices

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 or incident 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. An adjacent vertex distinguishing total-k-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 ^{\prime \prime }_{a}(G)\). It is known that \(\chi _{a}^{\prime \prime }(G)\le \Delta (G)+3\) for any planar graph with \(\Delta (G)\ge 10\). In this paper, we consider the list version of this coloring and show that if G is a planar graph with \(\Delta (G)\ge 11\), then \({ ch}_{a}^{\prime \prime }(G)\le \Delta (G)+3\), where \({ ch}^{\prime \prime }_a(G)\) is the adjacent vertex distinguishing total choosability.     

Improved upper bound for the degenerate and star chromatic numbers of graphs

Let \(G=G(V,E)\) be a graph. A proper coloring of G is a function \(f:V\rightarrow N\) such that \(f(x)\ne f(y)\) for every edge \(xy\in E\). A proper coloring of a graph G such that for every \(k\ge 1\), the union of any k color classes induces a \((k-1)\)-degenerate subgraph is called a degenerate coloring; a proper coloring of a graph with no two-colored \(P_{4}\) is called a star coloring. If a coloring is both degenerate and star, then we call it a degenerate star coloring of graph. The corresponding chromatic number is denoted as \(\chi _{sd}(G)\). In this paper, we employ entropy compression method to obtain a new upper bound \(\chi _{sd}(G)\le \lceil \frac{19}{6}\Delta ^{\frac{3}{2}}+5\Delta \rceil \) for general graph G.     

Algorithmic aspects of <Emphasis Type="Italic">b</Emphasis>-disjunctive domination in graphs

For a fixed integer \(b>1\), a set \(D\subseteq V\) is called a b-disjunctive dominating set of the graph \(G=(V,E)\) if for every vertex \(v\in V{\setminus }D\), v is either adjacent to a vertex of D or has at least b vertices in D at distance 2 from it. The Minimum b-Disjunctive Domination Problem (MbDDP) is to find a b-disjunctive dominating set of minimum cardinality. The cardinality of a minimum b-disjunctive dominating set of G is called the b-disjunctive domination number of G, and is denoted by \(\gamma _{b}^{d}(G)\). Given a positive integer k and a graph G, the b-Disjunctive Domination Decision Problem (bDDDP) is to decide whether G has a b-disjunctive dominating set of cardinality at most k. In this paper, we first show that for a proper interval graph G, \(\gamma _{b}^{d}(G)\) is equal to \(\gamma (G)\), the domination number of G for \(b \ge 3\) and observe that \(\gamma _{b}^{d}(G)\) need not be equal to \(\gamma (G)\) for \(b=2\). We then propose a polynomial time algorithm to compute a minimum cardinality b-disjunctive dominating set of a proper interval graph for \(b=2\). Next we tighten the NP-completeness of bDDDP by showing that it remains NP-complete even in chordal graphs. We also propose a \((\ln ({\varDelta }^{2}+(b-1){\varDelta }+b)+1)\)-approximation algorithm for MbDDP, where \({\varDelta }\) is the maximum degree of input graph \(G=(V,E)\) and prove that MbDDP cannot be approximated within \((1-\epsilon ) \ln (|V|)\) for any \(\epsilon >0\) unless NP \(\subseteq \) DTIME\((|V|^{O(\log \log |V|)})\). Finally, we show that MbDDP is APX-complete for bipartite graphs with maximum degree \(\max \{b,4\}\).     

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

Neighbor sum distinguishing total coloring of graphs with bounded treewidth

A proper total k-coloring \(\phi \) of a graph G is a mapping from \(V(G)\cup E(G)\) to \(\{1,2,\dots , k\}\) such that no adjacent or incident elements in \(V(G)\cup E(G)\) receive the same color. Let \(m_{\phi }(v)\) denote the sum of the colors on the edges incident with the vertex v and the color on v. A proper total k-coloring of G is called neighbor sum distinguishing if \(m_{\phi }(u)\not =m_{\phi }(v)\) for each edge \(uv\in E(G).\) Let \(\chi _{\Sigma }^t(G)\) be the neighbor sum distinguishing total chromatic number of a graph G. Pil?niak and Wo?niak conjectured that for any graph G, \(\chi _{\Sigma }^t(G)\le \Delta (G)+3\). In this paper, we show that if G is a graph with treewidth \(\ell \ge 3\) and \(\Delta (G)\ge 2\ell +3\), then \(\chi _{\Sigma }^t(G)\le \Delta (G)+\ell -1\). This upper bound confirms the conjecture for graphs with treewidth 3 and 4. Furthermore, when \(\ell =3\) and \(\Delta \ge 9\), we show that \(\Delta (G) + 1\le \chi _{\Sigma }^t(G)\le \Delta (G)+2\) and characterize graphs with equalities.     

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.     

Neighbor sum distinguishing list total coloring of subcubic graphs

Let \(G=(V, E)\) be a simple graph and denote the set of edges incident to a vertex v by E(v). The neighbor sum distinguishing (NSD) total choice number of G, denoted by \(\mathrm{ch}_{\Sigma }^{t}(G)\), is the smallest integer k such that, after assigning each \(z\in V\cup E\) a set L(z) of k real numbers, G has a total coloring \(\phi \) satisfying \(\phi (z)\in L(z)\) for each \(z\in V\cup E\) and \(\sum _{z\in E(u)\cup \{u\}}\phi (z)\ne \sum _{z\in E(v)\cup \{v\}}\phi (z)\) for each \(uv\in E\). In this paper, we propose some reducible configurations of NSD list total coloring for general graphs by applying the Combinatorial Nullstellensatz. As an application, we present that \(\mathrm{ch}^{t}_{\Sigma }(G)\le \Delta (G)+3\) for every subcubic graph G.     

Planar graphs without chordal 5-cycles are 2-good

Let G be a connected graph with \(n\ge 2\) vertices. Suppose that a fire breaks out at a vertex v of G. A firefighter starts to protect vertices. At each step, the firefighter protects two vertices not yet on fire. At the end of each step, the fire spreads to all the unprotected vertices that have a neighbour on fire. Let sn\(_2(v)\) denote the maximum number of vertices in G that the firefighter can save when a fire breaks out at vertex v. The 2-surviving rate \(\rho _2(G)\) of G is defined to be the real number \(\frac{1}{n^2} \sum _{v\in V(G)} \mathrm{sn}_2(v)\). Then it is obvious that \(0<\rho _2(G)<1\). The graph G is called 2-good if there is a constant \(c>0\) such that \(\rho _2(G)>c\). In this paper, we prove that every planar graph with \(n\ge 2\) vertices and without chordal 5-cycles is 2-good.     

Special Issue for FAW 2014

For a graph \(G=(V,E)\), a dominating set is a set \(D\subseteq V\) such that every vertex \(v\in V\setminus D\) has a neighbor in \(D\). The minimum outer-connected dominating set (Min-Outer-Connected-Dom-Set) problem for a graph \(G\) is to find a dominating set \(D\) of \(G\) such that \(G[V\setminus D]\), the induced subgraph by \(G\) on \(V\setminus D\), is connected and the cardinality of \(D\) is minimized. In this paper, we consider the complexity of the Min-Outer-Connected-Dom-Set problem. In particular, we show that the decision version of the Min-Outer-Connected-Dom-Set problem is NP-complete for split graphs, a well known subclass of chordal graphs. We also consider the approximability of the Min-Outer-Connected-Dom-Set problem. We show that the Min-Outer-Connected-Dom-Set problem cannot be approximated within a factor of \((1-\varepsilon ) \ln |V|\) for any \(\varepsilon >0\), unless NP \(\subseteq \) DTIME(\(|V|^{\log \log |V|}\)). For sufficiently large values of \(\varDelta \), we show that for graphs with maximum degree \(\varDelta \), the Min-Outer-Connected-Dom-Set problem cannot be approximated within a factor of \(\ln \varDelta -C \ln \ln \varDelta \) for some constant \(C\), unless P \(=\) NP. On the positive side, we present a \(\ln (\varDelta +1)+1\)-factor approximation algorithm for the Min-Outer-Connected-Dom-Set problem for general graphs. We show that the Min-Outer-Connected-Dom-Set problem is APX-complete for graphs of maximum degree 4.     

Neighbor sum distinguishing total coloring of 2-degenerate graphs

A proper k-total coloring of a graph G is a mapping from \(V(G)\cup E(G)\) to \(\{1,2,\ldots ,k\}\) such that no two adjacent or incident elements in \(V(G)\cup E(G)\) receive the same color. Let f(v) denote the sum of the colors on the edges incident with v and the color on vertex v. A proper k-total coloring of G is called neighbor sum distinguishing if \(f(u)\ne f(v)\) for each edge \(uv\in E(G)\). Let \(\chi ''_{\Sigma }(G)\) denote the smallest integer k in such a coloring of G. Pil?niak and Wo?niak conjectured that for any graph G, \(\chi ''_{\Sigma }(G)\le \Delta (G)+3\). In this paper, we show that if G is a 2-degenerate graph, then \(\chi ''_{\Sigma }(G)\le \Delta (G)+3\); Moreover, if \(\Delta (G)\ge 5\) then \(\chi ''_{\Sigma }(G)\le \Delta (G)+2\).     

A new sufficient condition for a tree T to have the (2, 1)-total number $$\Delta +1$$

A k-(2, 1)-total labelling of a graph G is a mapping \(f: V(G)\cup E(G)\rightarrow \{0,1,\ldots ,k\}\) such that adjacent vertices or adjacent edges receive distinct labels, and a vertex and its incident edges receive labels that differ in absolute value by at least 2. The (2, 1)-total number, denoted \(\lambda _2^t(G)\), is the minimum k such that G has a k-(2, 1)-total labelling. Let T be a tree with maximum degree \(\Delta \ge 7\). A vertex \(v\in V(T)\) is called major if \(d(v)=\Delta \), minor if \(d(v)<\Delta \), and saturated if v is major and is adjacent to exactly \(\Delta - 2\) major vertices. It is known that \(\Delta + 1 \le \lambda _2^t(T)\le \Delta + 2\). In this paper, we prove that if every major vertex is adjacent to at most \(\Delta -2\) major vertices, and every minor vertex is adjacent to at most three saturated vertices, then \(\lambda _2^t(T) = \Delta + 1\). The result is best possible with respect to these required conditions.     

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.     

Neighbor product distinguishing total colorings

A total-[k]-coloring of a graph G is a mapping \(\phi : V (G) \cup E(G)\rightarrow \{1, 2, \ldots , k\}\) such that any two adjacent elements in \(V (G) \cup E(G)\) receive different colors. Let f(v) denote the product of the color of a vertex v and the colors of all edges incident to v. A total-[k]-neighbor product distinguishing-coloring of G is a total-[k]-coloring of G such that \(f(u)\ne f(v)\), where \(uv\in E(G)\). By \(\chi ^{\prime \prime }_{\prod }(G)\), we denote the smallest value k in such a coloring of G. We conjecture that \(\chi _{\prod }^{\prime \prime }(G)\le \Delta (G)+3\) for any simple graph with maximum degree \(\Delta (G)\). In this paper, we prove that the conjecture holds for complete graphs, cycles, trees, bipartite graphs and subcubic graphs. Furthermore, we show that if G is a \(K_4\)-minor free graph with \(\Delta (G)\ge 4\), then \(\chi _{\prod }^{\prime \prime }(G)\le \Delta (G)+2\).     

On minimally 2-connected graphs with generalized connectivity $$\kappa _{3}=2$$

For \(S\subseteq G\), let \(\kappa (S)\) denote the maximum number r of edge-disjoint trees \(T_1, T_2, \ldots , T_r\) in G such that \(V(T_i)\cap V(T_j)=S\) for any \(i,j\in \{1,2,\ldots ,r\}\) and \(i\ne j\). For every \(2\le k\le n\), the k-connectivity of G, denoted by \(\kappa _k(G)\), is defined as \(\kappa _k(G)=\hbox {min}\{\kappa (S)| S\subseteq V(G)\ and\ |S|=k\}\). Clearly, \(\kappa _2(G)\) corresponds to the traditional connectivity of G. In this paper, we focus on the structure of minimally 2-connected graphs with \(\kappa _{3}=2\). Denote by \(\mathcal {H}\) the set of minimally 2-connected graphs with \(\kappa _{3}=2\). Let \(\mathcal {B}\subseteq \mathcal {H}\) and every graph in \(\mathcal {B}\) is either \(K_{2,3}\) or the graph obtained by subdividing each edge of a triangle-free 3-connected graph. We obtain that \(H\in \mathcal {H}\) if and only if \(H\in \mathcal {B}\) or H can be constructed from one or some graphs \(H_{1},\ldots ,H_{k}\) in \(\mathcal {B}\) (\(k\ge 1\)) by applying some operations recursively.     

Upper bounds of proper connection number of graphs

A total weighting of a graph G is a mapping \(\phi \) that assigns a weight to each vertex and each edge of G. The vertex-sum of \(v \in V(G)\) with respect to \(\phi \) is \(S_{\phi }(v)=\sum _{e\in E(v)}\phi (e)+\phi (v)\). A total weighting is proper if adjacent vertices have distinct vertex-sums. A graph \(G=(V,E)\) is called \((k,k')\)-choosable if the following is true: If each vertex x is assigned a set L(x) of k real numbers, and each edge e is assigned a set L(e) of \(k'\) real numbers, then there is a proper total weighting \(\phi \) with \(\phi (y)\in L(y)\) for any \(y \in V \cup E\). In this paper, we prove that for any graph \(G\ne K_1\), the Mycielski graph of G is (1,4)-choosable. Moreover, we give some sufficient conditions for the Mycielski graph of G to be (1,3)-choosable. In particular, our result implies that if G is a complete bipartite graph, a complete graph, a tree, a subcubic graph, a fan, a wheel, a Halin graph, or a grid, then the Mycielski graph of G is (1,3)-choosable.     

A $$(3,1)^{*}$$-choosable theorem on planar graphs

A list assignment of a graph G is a function L that assigns a list L(v) of colors to each vertex \(v\in V(G)\). An \((L,d)^*\)-coloring is a mapping \(\pi \) that assigns a color \(\pi (v)\in L(v)\) to each vertex \(v\in V(G)\) so that at most d neighbors of v receive color \(\pi (v)\). A graph G is said to be \((k,d)^*\)-choosable if it admits an \((L,d)^*\)-coloring for every list assignment L with \(|L(v)|\ge k\) for all \(v\in V(G)\). In this paper, we prove that every planar graph with neither adjacent triangles nor 6-cycles is \((3,1)^*\)-choosable. This is a partial answer to a question of Xu and Zhang (Discret Appl Math 155:74–78, 2007) that every planar graph without adjacent triangles is \((3,1)^*\)-choosable. Also, this improves a result in Lih et al. (Appl Math Lett 14:269–273, 2001) which says that every planar graph without 4- and 6-cycles is \((3,1)^*\)-choosable.