The <Emphasis Type="Italic">k</Emphasis>-metric dimension

The anti-Ramsey number AR(G, H) is defined to be the maximum number of colors in an edge coloring of G which doesn’t contain any rainbow subgraphs isomorphic to H. It is clear that there is an \(AR(K_{m,n},kK_2)\)-edge-coloring of \(K_{m,n}\) that doesn’t contain any rainbow \(kK_2\). In this paper, we show the uniqueness of this kind of \(AR(K_{m,n},kK_2)\)-edge-coloring of \(K_{m,n}\).     

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.     

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.     

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.     

Total coloring of planar graphs without adjacent short cycles

In the study of computer science, optimization, computation of Hessians matrix, graph coloring is an important tool. In this paper, we consider a classical coloring, total coloring. Let \(G=(V,E)\) be a graph. Total coloring is a coloring of \(V\cup {E}\) such that no two adjacent or incident elements (vertex/edge) receive the same color. Let G be a planar graph with \(\varDelta \ge 8\). We proved that if for every vertex \(v\in V\), there exists two integers \(i_v,j_v\in \{3,4,5,6,7\}\) such that v is not incident with adjacent \(i_v\)-cycles and \(j_v\)-cycles, then the total chromatic number of graph G is \(\varDelta +1\).     

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.     

Generalized acyclic edge colorings via entropy compression

An r-acyclic edge coloring of a graph G is a proper edge coloring such that any cycle C has at least \(\min \{|C|,r\}\) colors. The least number of colors needed for an r-acyclic edge coloring of G is called the r-acyclic edge chromatic number or the r-acyclic chromatic index of G, denoted by \(A'_{r}\left( G\right) \). In this paper, we study the r-acyclic edge chromatic number with \(r\ge 4\) and prove that \(A'_{r}\left( G\right) \le 2\Delta ^{\lfloor \tfrac{r}{2}\rfloor }+O\left( \Delta ^{\tfrac{r+1}{3}}\right) \). We also prove that when r is even, \(A'_{r}\left( G\right) \le \Delta ^{\tfrac{r}{2}}+O\left( \Delta ^{\tfrac{r+1}{3}}\right) \), which is asymptotically optimal. In addition, we investigate how the r-acyclic edge chromatic number performs as the girth increases. It is proved in this paper that for every graph G with girth at least \(2r-1\), \(A'_r\left( G\right) \le \left( 9r-7\right) \Delta +10r-12\) holds. Our approach is based on the entropy compression method.     

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

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

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

Trinque problem: covering complete graphs by plane degree-bounded hypergraphs

Let \(K_n\) be a complete graph drawn on the plane with every vertex incident to the infinite face. For any integers i and d, we define the (i, d)-Trinque Number of \(K_n\), denoted by \({\mathcal {T}}^d_{i}(K_n)\), as the smallest integer k such that there is an edge-covering of \(K_n\) by k “plane” hypergraphs of degree at most d and size of edge bounded by i. We compute this number for graphs (that is \(i=2\)) and gives some bounds for general hypergraphs.     

The $$(k,\ell )$$-proper index of graphs

A tree T in an edge-colored graph is called a proper tree if no two adjacent edges of T receive the same color. Let G be a connected graph of order n and k be an integer with \(2\le k \le n\). For \(S\subseteq V(G)\) and \(|S| \ge 2\), an S-tree is a tree containing the vertices of S in G. A set \(\{T_1,T_2,\ldots ,T_\ell \}\) of S-trees is called internally disjoint if \(E(T_i)\cap E(T_j)=\emptyset \) and \(V(T_i)\cap V(T_j)=S\) for \(1\le i\ne j\le \ell \). For a set S of k vertices of G, the maximum number of internally disjoint S-trees in G is denoted by \(\kappa (S)\). The k-connectivity \(\kappa _k(G)\) of G is defined by \(\kappa _k(G)=\min \{\kappa (S)\mid S\) is a k-subset of \(V(G)\}\). For a connected graph G of order n and for two integers k and \(\ell \) with \(2\le k\le n\) and \(1\le \ell \le \kappa _k(G)\), the \((k,\ell )\)-proper index \(px_{k,\ell }(G)\) of G is the minimum number of colors that are required in an edge-coloring of G such that for every k-subset S of V(G), there exist \(\ell \) internally disjoint proper S-trees connecting them. In this paper, we show that for every pair of positive integers k and \(\ell \) with \(k \ge 3\) and \(\ell \le \kappa _k(K_{n,n})\), there exists a positive integer \(N_1=N_1(k,\ell )\) such that \(px_{k,\ell }(K_n) = 2\) for every integer \(n \ge N_1\), and there exists also a positive integer \(N_2=N_2(k,\ell )\) such that \(px_{k,\ell }(K_{m,n}) = 2\) for every integer \(n \ge N_2\) and \(m=O(n^r) (r \ge 1)\). In addition, we show that for every \(p \ge c\root k \of {\frac{\log _a n}{n}}\) (\(c \ge 5\)), \(px_{k,\ell }(G_{n,p})\le 2\) holds almost surely, where \(G_{n,p}\) is the Erd?s–Rényi random graph model.     

Relation between the skew-rank of an oriented graph and the independence number of its underlying graph

An oriented graph \(G^\sigma \) is a digraph without loops or multiple arcs whose underlying graph is G. Let \(S\left( G^\sigma \right) \) be the skew-adjacency matrix of \(G^\sigma \) and \(\alpha (G)\) be the independence number of G. The rank of \(S(G^\sigma )\) is called the skew-rank of \(G^\sigma \), denoted by \(sr(G^\sigma )\). Wong et al. (Eur J Comb 54:76–86, 2016) studied the relationship between the skew-rank of an oriented graph and the rank of its underlying graph. In this paper, the correlation involving the skew-rank, the independence number, and some other parameters are considered. First we show that \(sr(G^\sigma )+2\alpha (G)\geqslant 2|V_G|-2d(G)\), where \(|V_G|\) is the order of G and d(G) is the dimension of cycle space of G. We also obtain sharp lower bounds for \(sr(G^\sigma )+\alpha (G),\, sr(G^\sigma )-\alpha (G)\), \(sr(G^\sigma )/\alpha (G)\) and characterize all corresponding extremal graphs.     

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

Computing the <Emphasis Type="Italic">k</Emphasis>-resilience of a synchronized multi-robot system

The vertex arboricity va(G) of a graph G is the minimum number of colors the vertices can be colored so that each color class induces a forest. It was known that \(va(G)\le 3\) for every planar graph G. In this paper, we prove that \(va(G)\le 2\) if G is a planar graph without intersecting 5-cycles.     

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.     

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

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.     

On the b-coloring of tight graphs

A coloring c of a graph \(G=(V,E)\) is a b -coloring if for every color i there is a vertex, say w(i), of color i whose neighborhood intersects every other color class. The vertex w(i) is called a b-dominating vertex of color i. The b -chromatic number of a graph G, denoted by b(G), is the largest integer k such that G admits a b-coloring with k colors. Let m(G) be the largest integer m such that G has at least m vertices of degree at least \(m-1\). A graph G is tight if it has exactly m(G) vertices of degree \(m(G)-1\), and any other vertex has degree at most \(m(G)-2\). In this paper, we show that the b-chromatic number of tight graphs with girth at least 8 is at least \(m(G)-1\) and characterize the graphs G such that \(b(G)=m(G)\). Lin and Chang (2013) conjectured that the b-chromatic number of any graph in \(\mathcal {B}_{m}\) is m or \(m-1\) where \(\mathcal {B}_{m}\) is the class of tight bipartite graphs \((D,D{^\prime })\) of girth 6 such that D is the set of vertices of degree \(m-1\). We verify the conjecture of Lin and Chang for some subclass of \(\mathcal {B}_{m}\), and we give a lower bound for any graph in \(\mathcal {B}_{m}\).