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

Modified linear programming and class 0 bounds for graph pebbling

Given a configuration of pebbles on the vertices of a connected graph G, a pebbling move removes two pebbles from some vertex and places one pebble on an adjacent vertex. The pebbling number of a graph G is the smallest integer k such that for each vertex v and each configuration of k pebbles on G there is a sequence of pebbling moves that places at least one pebble on v. First, we improve on results of Hurlbert, who introduced a linear optimization technique for graph pebbling. In particular, we use a different set of weight functions, based on graphs more general than trees. We apply this new idea to some graphs from Hurlbert’s paper to give improved bounds on their pebbling numbers. Second, we investigate the structure of Class 0 graphs with few edges. We show that every n-vertex Class 0 graph has at least \(\frac{5}{3}n - \frac{11}{3}\) edges. This disproves a conjecture of Blasiak et al. For diameter 2 graphs, we strengthen this lower bound to \(2n - 5\), which is best possible. Further, we characterize the graphs where the bound holds with equality and extend the argument to obtain an identical bound for diameter 2 graphs with no cut-vertex.     

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.     

On (<Emphasis Type="Italic">s</Emphasis>, <Emphasis Type="Italic">t</Emphasis>)-relaxed strong edge-coloring of graphs

In this paper, we introduce a new relaxation of strong edge-coloring. Let G be a graph. For two nonnegative integers s and t, an (s, t)-relaxed strong k-edge-coloring is an assignment of k colors to the edges of G, such that for any edge e, there are at most s edges adjacent to e and t edges which are distance two apart from e assigned the same color as e. The (s, t)-relaxed strong chromatic index, denoted by \({\chi '}_{(s,t)}(G)\), is the minimum number k of an (s, t)-relaxed strong k-edge-coloring admitted by G. This paper studies the (s, t)-relaxed strong edge-coloring of graphs, especially trees. For a tree T, the tight upper bounds for \({\chi '}_{(s,0)}(T)\) and \({\chi '}_{(0,t)}(T)\) are given. And the (1, 1)-relaxed strong chromatic index of an infinite regular tree is determined. Further results on \({\chi '}_{(1,0)}(T)\) are also presented.     

A sufficient condition for planar graphs to be (3, 1)-choosable

A (k, d)-list assignment L of a graph is a function that assigns to each vertex v a list L(v) of at least k colors satisfying \(|L(x)\cap L(y)|\le d\) for each edge xy. An L-coloring is a vertex coloring \(\pi \) such that \(\pi (v) \in L(v)\) for each vertex v and \(\pi (x) \ne \pi (y)\) for each edge xy. A graph G is (k, d)-choosable if there exists an L-coloring of G for every (k, d)-list assignment L. This concept is known as choosability with separation. In this paper, we will use Thomassen list coloring extension method to prove that planar graphs with neither 6-cycles nor adjacent 4- and 5-cycles are (3, 1)-choosable. This is a strengthening of a result obtained by using Discharging method which says that planar graphs without 5- and 6-cycles are (3, 1)-choosable.     

Note on incidence chromatic number of subquartic graphs

An incidence in a graph G is a pair (v, e) where v is a vertex of G and e is an edge of G incident to v. Two incidences (v, e) and (u, f) are adjacent if at least one of the following holds: \((a) v = u, (b) e = f\), or \((c) vu \in \{e,f\}\). An incidence coloring of G is a coloring of its incidences assigning distinct colors to adjacent incidences. In this note we prove that every subquartic graph admits an incidence coloring with at most seven colors.     

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.     

Neighbor sum distinguishing index of 2-degenerate graphs

We consider proper edge colorings of a graph G using colors in \(\{1,\ldots ,k\}\). Such a coloring is called neighbor sum distinguishing if for each pair of adjacent vertices u and v, the sum of the colors of the edges incident with u is different from the sum of the colors of the edges incident with v. The smallest value of k in such a coloring of G is denoted by \({\mathrm ndi}_{\Sigma }(G)\). In this paper we show that if G is a 2-degenerate graph without isolated edges, then \({\mathrm ndi}_{\Sigma }(G)\le \max \{\Delta (G)+2,7\}\).     

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.     

Erdős–Gallai-type results for colorful monochromatic connectivity of a graph

A path in an edge-colored graph is called a monochromatic path if all the edges on the path are colored with one same color. An edge-coloring of G is a monochromatic connection coloring (MC-coloring, for short) if there is a monochromatic path joining any two vertices in G. For a connected graph G, the monochromatic connection number of G, denoted by mc(G), is defined to be the maximum number of colors used in an MC-coloring of G. These concepts were introduced by Caro and Yuster, and they got some nice results. In this paper, we study two kinds of Erd?s–Gallai-type problems for mc(G), and completely solve them.     

Rainbow connection numbers of Cayley graphs

An edge colored graph is rainbow connected if any two vertices are connected by a path whose edges have distinct colors. The rainbow connection number, rc-number for short, of a graph \({\varGamma }\), is the smallest number of colors that are needed in order to make \({\varGamma }\) rainbow connected. In this paper, we give a method to bound the rc-numbers of graphs with certain structural properties. Using this method, we investigate the rc-numbers of Cayley graphs, especially, those defined on abelian groups and on dihedral groups.     

On vertex-parity edge-colorings

A vertex signature \(\pi \) of a finite graph G is any mapping \(\pi \,{:}\,V(G)\rightarrow \{0,1\}\). An edge-coloring of G is said to be vertex-parity for the pair \((G,\pi )\) if for every vertex v each color used on the edges incident to v appears in parity accordance with \(\pi \), i.e. an even or odd number of times depending on whether \(\pi (v)\) equals 0 or 1, respectively. The minimum number of colors for which \((G,\pi )\) admits such an edge-coloring is denoted by \(\chi '_p(G,\pi )\). We characterize the existence and prove that \(\chi '_p(G,\pi )\) is at most 6. Furthermore, we give a structural characterization of the pairs \((G,\pi )\) for which \(\chi '_p(G,\pi )=5\) and \(\chi '_p(G,\pi )=6\). In the last part of the paper, we consider a weaker version of the coloring, where it suffices that at every vertex, at least one color appears in parity accordance with \(\pi \). We show that the corresponding chromatic index is at most 3 and give a complete characterization for it.     

The <Emphasis Type="Italic">k</Emphasis>-hop connected dominating set problem: approximation and hardness

Let G be a connected graph and k be a positive integer. A vertex subset D of G is a k-hop connected dominating set if the subgraph of G induced by D is connected, and for every vertex v in G there is a vertex u in D such that the distance between v and u in G is at most k. We study the problem of finding a minimum k-hop connected dominating set of a graph (\({\textsc {Min}}k{\hbox {-}\textsc {CDS}}\)). We prove that \({\textsc {Min}}k{\hbox {-}\textsc {CDS}}\) is \(\mathscr {NP}\)-hard on planar bipartite graphs of maximum degree 4. We also prove that \({\textsc {Min}}k{\hbox {-}\textsc {CDS}}\) is \(\mathscr {APX}\)-complete on bipartite graphs of maximum degree 4. We present inapproximability thresholds for \({\textsc {Min}}k{\hbox {-}\textsc {CDS}}\) on bipartite and on (1, 2)-split graphs. Interestingly, one of these thresholds is a parameter of the input graph which is not a function of its number of vertices. We also discuss the complexity of computing this graph parameter. On the positive side, we show an approximation algorithm for \({\textsc {Min}}k{\hbox {-}\textsc {CDS}}\). Finally, when \(k=1\), we present two new approximation algorithms for the weighted version of the problem restricted to graphs with a polynomially bounded number of minimal separators.     

Extremal coloring for the anti-Ramsey problem of matchings in complete graphs

Given a graph G, the anti-Ramsey number \(AR(K_n,G)\) is defined to be the maximum number of colors in an edge-coloring of \(K_n\) which does not contain any rainbow G (i.e., all the edges of G have distinct colors). The anti-Ramsey number was introduced by Erd?s et al. (Infinite and finite sets, pp 657–665, 1973) and so far it has been determined for several special graph classes. Another related interesting problem posed by Erd?s et al. is the uniqueness of the extremal coloring for the anti-Ramsey number. Contrary to the anti-Ramsey number, there are few results about the extremal coloring. In this paper, we show the uniqueness of such extremal coloring for the anti-Ramsey number of matchings in the complete graph.     

A linear-time algorithm for clique-coloring problem in circular-arc graphs

A maximal clique of G is a clique not properly contained in any other clique. A k-clique-coloring of a graph G is an assignment of k colors to the vertices of G such that no maximal clique with at least two vertices is monochromatic. The smallest integer k admitting a k-clique-coloring of G is called clique-coloring number of G. Cerioli and Korenchendler (Electron Notes Discret Math 35:287–292, 2009) showed that there is a polynomial-time algorithm to solve the clique-coloring problem in circular-arc graphs and asked whether there exists a linear-time algorithm to find an optimal clique-coloring in circular-arc graphs or not. In this paper we present a linear-time algorithm of the optimal clique-coloring in circular-arc graphs.     

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.     

Is there any polynomial upper bound for the universal labeling of graphs?

A universal labeling of a graph G is a labeling of the edge set in G such that in every orientation \(\ell \) of G for every two adjacent vertices v and u, the sum of incoming edges of v and u in the oriented graph are different from each other. The universal labeling number of a graph G is the minimum number k such that G has universal labeling from \(\{1,2,\ldots , k\}\) denoted it by \(\overrightarrow{\chi _{u}}(G) \). We have \(2\Delta (G)-2 \le \overrightarrow{\chi _{u}} (G)\le 2^{\Delta (G)}\), where \(\Delta (G)\) denotes the maximum degree of G. In this work, we offer a provocative question that is: “Is there any polynomial function f such that for every graph G, \(\overrightarrow{\chi _{u}} (G)\le f(\Delta (G))\)?”. Towards this question, we introduce some lower and upper bounds on their parameter of interest. Also, we prove that for every tree T, \(\overrightarrow{\chi _{u}}(T)={\mathcal {O}}(\Delta ^3) \). Next, we show that for a given 3-regular graph G, the universal labeling number of G is 4 if and only if G belongs to Class 1. Therefore, for a given 3-regular graph G, it is an \( {{\mathbf {N}}}{{\mathbf {P}}} \)-complete to determine whether the universal labeling number of G is 4. Finally, using probabilistic methods, we almost confirm a weaker version of the problem.     

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-sum-distinguishing edge choosability of subcubic graphs

A graph G is said to be neighbor-sum-distinguishing edge k-choose if, for every list L of colors such that L(e) is a set of k positive real numbers for every edge e, there exists a proper edge coloring which assigns to each edge a color from its list so that for each pair of adjacent vertices u and v the sum of colors taken on the edges incident to u is different from the sum of colors taken on the edges incident to v. Let \(\mathrm{ch}^{\prime }_{\sum ^p}(G)\) denote the smallest integer k such that G is neighbor-sum-distinguishing edge k-choose. In this paper, we prove that if G is a subcubic graph with the maximum average degree mad(G), then (1) \(\mathrm{ch}^{\prime }_{\sum ^p}(G)\le 7\); (2) \(\mathrm{ch}^{\prime }_{\sum ^p}(G)\le 6\) if \(\hbox {mad}(G)<\frac{36}{13}\); (3) \(\mathrm{ch}^{\prime }_{\sum ^p}(G)\le 5\) if \(\hbox {mad}(G)<\frac{5}{2}\).     

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.