Minimum 2-distance coloring of planar graphs and channel assignment

A 2-distance k-coloring of a graph G is a proper k-coloring such that any two vertices at distance two get different colors. \(\chi _{2}(G)\)=min{k|G has a 2-distance k-coloring}. Wegner conjectured that for each planar graph G with maximum degree \(\Delta \), \(\chi _2(G) \le 7\) if \(\Delta \le 3\), \(\chi _2(G) \le \Delta +5\) if \(4\le \Delta \le 7\) and \(\chi _2(G) \le \lfloor \frac{3\Delta }{2}\rfloor +1\) if \(\Delta \ge 8\). In this paper, we prove that: (1) If G is a planar graph with maximum degree \(\Delta \le 5\), then \(\chi _{2}(G)\le 20\); (2) If G is a planar graph with maximum degree \(\Delta \ge 6\), then \(\chi _{2}(G)\le 5\Delta -7\).     

Embeddings into almost self-centered graphs of given radius

A graph is almost self-centered (ASC) if all but two of its vertices are central. An almost self-centered graph with radius r is called an r-ASC graph. The r-ASC index \(\theta _r(G)\) of a graph G is the minimum number of vertices needed to be added to G such that an r-ASC graph is obtained that contains G as an induced subgraph. It is proved that \(\theta _r(G)\le 2r\) holds for any graph G and any \(r\ge 2\) which improves the earlier known bound \(\theta _r(G)\le 2r+1\). It is further proved that \(\theta _r(G)\le 2r-1\) holds if \(r\ge 3\) and G is of order at least 2. The 3-ASC index of complete graphs is determined. It is proved that \(\theta _3(G)\in \{3,4\}\) if G has diameter 2 and for several classes of graphs of diameter 2 the exact value of the 3-ASC index is obtained. For instance, if a graph G of diameter 2 does not contain a diametrical triple, then \(\theta _3(G) = 4\). The 3-ASC index of paths of order \(n\ge 1\), cycles of order \(n\ge 3\), and trees of order \(n\ge 10\) and diameter \(n-2\) are also determined, respectively, and several open problems proposed.     

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

Distance domination in graphs with given minimum and maximum degree

For an integer \(k \ge 1\), a distance k-dominating set of a connected graph G is a set S of vertices of G such that every vertex of V(G) is at distance at most k from some vertex of S. The distance k-domination number \(\gamma _k(G)\) of G is the minimum cardinality of a distance k-dominating set of G. In this paper, we establish an upper bound on the distance k-domination number of a graph in terms of its order, minimum degree and maximum degree. We prove that for \(k \ge 2\), if G is a connected graph with minimum degree \(\delta \ge 2\) and maximum degree \(\Delta \) and of order \(n \ge \Delta + k - 1\), then \(\gamma _k(G) \le \frac{n + \delta - \Delta }{\delta + k - 1}\). This result improves existing known results.     

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.     

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.     

A new graph parameter and a construction of larger graph without increasing radio <Emphasis Type="Italic">k</Emphasis>-chromatic number

For a positive integer \(k\ge 2\), the radio k-coloring problem is an assignment L of non-negative integers (colors) to the vertices of a finite simple graph G satisfying the condition \(|L(u)-L(v)| \ge k+1-d(u,v)\), for any two distinct vertices u, v of G and d(u, v) being distance between u, v. The span of L is the largest integer assigned by L, while 0 is taken as the smallest color. An \(rc_k\)-coloring on G is a radio k-coloring on G of minimum span which is referred as the radio k-chromatic number of G and denoted by \(rc_k(G)\). An integer h, \(0<h<rc_k(G)\), is a hole in a \(rc_k\)-coloring on G if h is not assigned by it. In this paper, we construct a larger graph from a graph of a certain class by using a combinatorial property associated with \((k-1)\) consecutive holes in any \(rc_k\)-coloring of a graph. Exploiting the same property, we introduce a new graph parameter, referred as \((k-1)\)-hole index of G and denoted by \(\rho _k(G)\). We also explore several properties of \(\rho _k(G)\) including its upper bound and relation with the path covering number of the complement \(G^c\).     

Upper bounds for adjacent vertex-distinguishing edge coloring

An adjacent vertex-distinguishing edge coloring of a graph is a proper edge coloring such that no pair of adjacent vertices meets the same set of colors. The adjacent vertex-distinguishing edge chromatic number is the minimum number of colors required for an adjacent vertex-distinguishing edge coloring, denoted as \(\chi '_{as}(G)\). In this paper, we prove that for a connected graph G with maximum degree \(\Delta \ge 3\), \(\chi '_{as}(G)\le 3\Delta -1\), which proves the previous upper bound. We also prove that for a graph G with maximum degree \(\Delta \ge 458\) and minimum degree \(\delta \ge 8\sqrt{\Delta ln \Delta }\), \(\chi '_{as}(G)\le \Delta +1+5\sqrt{\Delta ln \Delta }\).     

Total coloring of planar graphs without adjacent chordal 6-cycles

A total coloring of a graph G is a coloring such that no two adjacent or incident elements receive the same color. In this field there is a famous conjecture, named Total Coloring Conjecture, saying that the the total chromatic number of each graph G is at most \(\Delta +2\). Let G be a planar graph with maximum degree \(\Delta \ge 7\) and without adjacent chordal 6-cycles, that is, two cycles of length 6 with chord do not share common edges. In this paper, it is proved that the total chromatic number of G is \(\Delta +1\), which partly confirmed Total Coloring Conjecture.     

Equitable colorings of Cartesian products of square of cycles and paths with complete bipartite graphs

A graph G is said to be equitably k-colorable if the vertex set of G can be divided into k independent sets for which any two sets differ in size at most one. The equitable chromatic number of G, \(\chi _{=}(G)\), is the minimum k for which G is equitably k-colorable. The equitable chromatic threshold of G, \(\chi _{=}^{*}(G)\), is the minimum k for which G is equitably \(k'\)-colorable for all \(k'\ge k\). In this paper, the exact values of \(\chi _{=}^{*}(G\Box H)\) and \(\chi _{=}(G\Box H)\) are obtained when G is the square of a cycle or a path and H is a complete bipartite graph.     

Minimum choosability of planar graphs

The problem of list coloring of graphs appears in practical problems concerning channel or frequency assignment. In this paper, we study the minimum number of choosability of planar graphs. A graph G is edge-k-choosable if whenever every edge x is assigned with a list of at least k colors, L(x)), there exists an edge coloring \(\phi \) such that \(\phi (x) \in L(x)\). Similarly, A graph G is toal-k-choosable if when every element (edge or vertex) x is assigned with a list of at least k colors, L(x), there exists an total coloring \(\phi \) such that \(\phi (x) \in L(x)\). We proved \(\chi '_{l}(G)=\Delta \) and \(\chi ''_{l}(G)=\Delta +1\) for a planar graph G with maximum degree \(\Delta \ge 8\) and without chordal 6-cycles, where the list edge chromatic number \(\chi '_{l}(G)\) of G is the smallest integer k such that G is edge-k-choosable and the list total chromatic number \(\chi ''_{l}(G)\) of G is the smallest integer k such that G is total-k-choosable.     

Total coloring of 1-toroidal graphs with maximum degree at least 11 and no adjacent triangles

A total coloring of a graph G is an assignment of colors to the vertices and the edges of G such that every pair of adjacent/incident elements receive distinct colors. The total chromatic number of a graph G, denoted by \(\chi ''(G)\), is the minimum number of colors in a total coloring of G. The well-known total coloring conjecture (TCC) says that every graph with maximum degree \(\Delta \) admits a total coloring with at most \(\Delta + 2\) colors. A graph is 1-toroidal if it can be drawn in torus such that every edge crosses at most one other edge. In this paper, we investigate the total coloring of 1-toroidal graphs, and prove that the TCC holds for the 1-toroidal graphs with maximum degree at least 11 and some restrictions on the triangles. Consequently, if G is a 1-toroidal graph with maximum degree \(\Delta \) at least 11 and without adjacent triangles, then G admits a total coloring with at most \(\Delta + 2\) colors.     

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

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.     

Nordhaus–Gaddum bounds for total Roman domination

A Nordhaus–Gaddum-type result is a lower or an upper bound on the sum or the product of a parameter of a graph and its complement. In this paper we continue the study of Nordhaus–Gaddum bounds for the total Roman domination number \(\gamma _{tR}\). Let G be a graph on n vertices and let \(\overline{G}\) denote the complement of G, and let \(\delta ^*(G)\) denote the minimum degree among all vertices in G and \(\overline{G}\). For \(\delta ^*(G)\ge 1\), we show that (i) if G and \(\overline{G}\) are connected, then \((\gamma _{tR}(G)-4)(\gamma _{tR}(\overline{G})-4)\le 4\delta ^*(G)-4\), (ii) if \(\gamma _{tR}(G), \gamma _{tR}(\overline{G})\ge 8\), then \(\gamma _{tR}(G)+\gamma _{tR}(\overline{G})\le 2\delta ^*(G)+5\) and (iii) \(\gamma _{tR}(G)+\gamma _{tR}(\overline{G})\le n+5\) and \(\gamma _{tR}(G)\gamma _{tR}(\overline{G})\le 6n-5\).     

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.     

On zero-sum $$\mathbb {Z}_{2j}^k$$-magic graphs

Let \(G = (V,E)\) be a finite graph and let \((\mathbb {A},+)\) be an abelian group with identity 0. Then G is \(\mathbb {A}\)-magic if and only if there exists a function \(\phi \) from E into \(\mathbb {A} - \{0\}\) such that for some \(c \in \mathbb {A}, \sum _{e \in E(v)} \phi (e) = c\) for every \(v \in V\), where E(v) is the set of edges incident to v. Additionally, G is zero-sum \(\mathbb {A}\)-magic if and only if \(\phi \) exists such that \(c = 0\). We consider zero-sum \(\mathbb {A}\)-magic labelings of graphs, with particular attention given to \(\mathbb {A} = \mathbb {Z}_{2j}^k\). For \(j \ge 1\), let \(\zeta _{2j}(G)\) be the smallest positive integer c such that G is zero-sum \(\mathbb {Z}_{2j}^c\)-magic if c exists; infinity otherwise. We establish upper bounds on \(\zeta _{2j}(G)\) when \(\zeta _{2j}(G)\) is finite, and show that \(\zeta _{2j}(G)\) is finite for all r-regular \(G, r \ge 2\). Appealing to classical results on the factors of cubic graphs, we prove that \(\zeta _4(G) \le 2\) for a cubic graph G, with equality if and only if G has no 1-factor. We discuss the problem of classifying cubic graphs according to the collection of finite abelian groups for which they are zero-sum group-magic.     

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

Paired-domination number of claw-free odd-regular graphs

A paired-dominating set of a graph G is a dominating set of vertices whose induced subgraph has a perfect matching, while the paired-domination number is the minimum cardinality of a paired-dominating set in the graph, denoted by \(\gamma _{pr}(G)\). Let G be a connected \(\{K_{1,3}, K_{4}-e\}\)-free cubic graph of order n. We show that \(\gamma _{pr}(G)\le \frac{10n+6}{27}\) if G is \(C_{4}\)-free and that \(\gamma _{pr}(G)\le \frac{n}{3}+\frac{n+6}{9(\lceil \frac{3}{4}(g_o+1)\rceil +1)}\) if G is \(\{C_{4}, C_{6}, C_{10}, \ldots , C_{2g_o}\}\)-free for an odd integer \(g_o\ge 3\); the extremal graphs are characterized; we also show that if G is a 2 -connected, \(\gamma _{pr}(G) = \frac{n}{3} \). Furthermore, if G is a connected \((2k+1)\)-regular \(\{K_{1,3}, K_4-e\}\)-free graph of order n, then \(\gamma _{pr}(G)\le \frac{n}{k+1} \), with equality if and only if \(G=L(F)\), where \(F\cong K_{1, 2k+2}\), or k is even and \(F\cong K_{k+1,k+2}\).     

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.