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 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 colorings of planar graphs with girth at least five

An adjacent vertex distinguishing edge coloring of a graph \(G\) is a proper edge coloring of \(G\) such that any pair of adjacent vertices admit different sets of colors. The minimum number of colors required for such a coloring of \(G\) is denoted by \(\chi ^{\prime }_{a}(G)\) . In this paper, we prove that if \(G\) is a planar graph with girth at least 5 and \(G\) is not a 5-cycle, then \(\chi ^{\prime }_{a}(G)\le \Delta +2\) , where \(\Delta \) is the maximum degree of \(G\) . This confirms partially a conjecture in Zhang et al. (Appl Math Lett 15:623–626, 2002).     

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.     

Parity and strong parity edge-colorings of graphs

A parity walk in an edge-coloring of a graph is a walk along which each color is used an even number of times. A parity edge-coloring (respectively, strong parity edge-coloring) is an edge-coloring in which there is no nontrivial parity path (respectively, open parity walk). The parity edge-chromatic number p(G) (respectively, strong parity edge-chromatic number $\widehat{p}(G)$ ) is the least number of colors in a parity edge-coloring (respectively, strong parity edge-coloring) of G. Notice that $\widehat{p}(G) \ge p(G) \ge \chi'(G) \ge \Delta(G)$ for any graph G. In this paper, we determine $\widehat{p}(G)$ and p(G) for some complete bipartite graphs and some products of graphs. For instance, we determine $\widehat{p}(K_{m,n})$ and p(K _m,n ) for m≤n with n≡0,?1,?2 (mod 2^?lg?m?).     

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.     

Minimum statuses of connected graphs with fixed maximum degree and order

The status of a vertex in a connected graph is the sum of distances between the vertex and all vertices. The minimum status of a connected graph is the minimum of statuses of all vertices of this graph. In this paper we obtain the sharp lower bound and the sharp upper bound on the minimum status of a connected graph with maximum degree k and order n. All the graphs attaining the lower bound are obtained, and a necessary condition is given for those graphs attaining the upper bound.     

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.     

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

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.     

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.     

Reconfiguration graphs for vertex colourings of chordal and chordal bipartite graphs

A k-colouring of a graph G=(V,E) is a mapping c:V→{1,2,…,k} such that c(u)≠c(v) whenever uv is an edge. The reconfiguration graph of the k-colourings of G contains as its vertex set the k-colourings of G, and two colourings are joined by an edge if they differ in colour on just one vertex of G. We introduce a class of k-colourable graphs, which we call k-colour-dense graphs. We show that for each k-colour-dense graph G, the reconfiguration graph of the ?-colourings of G is connected and has diameter O(|V|²), for all ?≥k+1. We show that this graph class contains the k-colourable chordal graphs and that it contains all chordal bipartite graphs when k=2. Moreover, we prove that for each k≥2 there is a k-colourable chordal graph G whose reconfiguration graph of the (k+1)-colourings has diameter Θ(|V|²).     

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.     

Sparse multipartite graphs as partition universal for graphs with bounded degree

For graphs G and H, let \(G\rightarrow (H,H)\) signify that any red/blue edge coloring of G contains a monochromatic H as a subgraph. Denote \(\mathcal {H}(\Delta ,n)=\{H:|V(H)|=n,\Delta (H)\le \Delta \}\). For any \(\Delta \) and n, we say that G is partition universal for \(\mathcal {H}(\Delta ,n)\) if \(G\rightarrow (H,H)\) for every \(H\in \mathcal {H}(\Delta ,n)\). Let \(G_r(N,p)\) be the random spanning subgraph of the complete r-partite graph \(K_r(N)\) with N vertices in each part, in which each edge of \(K_r(N)\) appears with probability p independently and randomly. We prove that for fixed \(\Delta \ge 2\) there exist constants r, B and C depending only on \(\Delta \) such that if \(N\ge Bn\) and \(p=C(\log N/N)^{1/\Delta }\), then asymptotically almost surely \(G_r(N,p)\) is partition universal for \(\mathcal {H}(\Delta ,n)\).     

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.     

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

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 maximum Wiener index of trees and graphs with given radius

Let G be a connected graph of order n. The long-standing open and close problems in distance graph theory are: what is the Wiener index W(G) or average distance \(\mu (G)\) among all graphs of order n with diameter d (radius r)? There are very few number of articles where were worked on the relationship between radius or diameter and Wiener index. In this paper, we give an upper bound on Wiener index of trees and graphs in terms of number of vertices n, radius r, and characterize the extremal graphs. Moreover, from this result we give an upper bound on \(\mu (G)\) in terms of order and independence number of graph G. Also we present another upper bound on Wiener index of graphs in terms of number of vertices n, radius r and maximum degree \(\Delta \), and characterize the extremal graphs.