Neighbor sums distinguishing total colorings of planar graphs without short cycles. (English) Zbl 1342.05045
A \(k\)-total coloring of a graph \(G(V,E)\) is a mapping \(\phi:V\cup E\to \{1,2,3,\ldots, k\}\) such that (i) every pair of adjacent vertices has distinct colors, (ii) every pair of adjacent edges has distinct colors, and (iii) every vertex \(v\) and every edge incident to \(v\) have distinct colors.
Let \(f(v)\) denote the total sum of colors of the edges incident to the vertex \(v\) in \(G\). Then, a \(k\)-neighbourhood sum distinguishing total coloring of \(G\), denoted by \(\chi_{\mathrm{nsd}}^{\prime\prime}(G)\), is a \(k\)-total coloring of \(G\) such that \(f(u)\neq f(v)\) for each edge \(uv\in E(G)\).
There is a conjecture on \(k\)-neighbourhood sum distinguishing total colorings of a graph \(G\) having at least two vertices that \(\chi_{\mathrm{nsd}}^{\prime\prime}(G)\leq \Delta(G)+3\).
In this paper, the authors establish this conjecture for planar graphs with \(\Delta(G)\geq 5\), which do not consist of \(3\)-cycles or \(4\)-cycles. The proof of the theorem progresses in the method “Reductio ad absurdum”. They assume that this statement not true.
Then, they establish some claims in the proof. The first claim settled in the proof is that for each \(3^-\)-vertex \(u\), \(d_{3^-}(u)=0\). This part is also proved using the contradiction method.
Then, the authors claim that every \(4\)-vertex of \(G\) has at most one \(2^-\) vertex and if \(d_2^-(u)=1\), then \(d_3(u)=0\). The third claim is that if \(u\) is an \(l\)-vertex of \(G\) with \(l\geq 5\), then \(d_{2^-}(u)\leq \lfloor\frac{l}{2}\rfloor\) and if \(d(u)=6\), then \(d_1(u)\leq 2\). The fourth claim states that if \(d_H(u)=3\), then \(u\) is not adjacent to any other \(3^-\)-vertex in \(H\), where \(H\) is the graph obtained from \(G\) by removing all its leaves. In the fifth claim, the authors prove that in a graph \(H\), if \(d_H(u)=4\) and \(d_2^H=1\), then \(d_3^H=0\). All these claims are proved using the contradiction method.
In view of these five claims and Euler’s formula for planar graphs, the authors design a discharging rule and redistribute the weights accordingly. Based on this discharging rule, analysing different possible cases, they finally reach at a contradiction to the initial assumption. The article is well written and the presentation is logically and mathematically sound. Hence, reading this article provides a delightful experience.
Let \(f(v)\) denote the total sum of colors of the edges incident to the vertex \(v\) in \(G\). Then, a \(k\)-neighbourhood sum distinguishing total coloring of \(G\), denoted by \(\chi_{\mathrm{nsd}}^{\prime\prime}(G)\), is a \(k\)-total coloring of \(G\) such that \(f(u)\neq f(v)\) for each edge \(uv\in E(G)\).
There is a conjecture on \(k\)-neighbourhood sum distinguishing total colorings of a graph \(G\) having at least two vertices that \(\chi_{\mathrm{nsd}}^{\prime\prime}(G)\leq \Delta(G)+3\).
In this paper, the authors establish this conjecture for planar graphs with \(\Delta(G)\geq 5\), which do not consist of \(3\)-cycles or \(4\)-cycles. The proof of the theorem progresses in the method “Reductio ad absurdum”. They assume that this statement not true.
Then, they establish some claims in the proof. The first claim settled in the proof is that for each \(3^-\)-vertex \(u\), \(d_{3^-}(u)=0\). This part is also proved using the contradiction method.
Then, the authors claim that every \(4\)-vertex of \(G\) has at most one \(2^-\) vertex and if \(d_2^-(u)=1\), then \(d_3(u)=0\). The third claim is that if \(u\) is an \(l\)-vertex of \(G\) with \(l\geq 5\), then \(d_{2^-}(u)\leq \lfloor\frac{l}{2}\rfloor\) and if \(d(u)=6\), then \(d_1(u)\leq 2\). The fourth claim states that if \(d_H(u)=3\), then \(u\) is not adjacent to any other \(3^-\)-vertex in \(H\), where \(H\) is the graph obtained from \(G\) by removing all its leaves. In the fifth claim, the authors prove that in a graph \(H\), if \(d_H(u)=4\) and \(d_2^H=1\), then \(d_3^H=0\). All these claims are proved using the contradiction method.
In view of these five claims and Euler’s formula for planar graphs, the authors design a discharging rule and redistribute the weights accordingly. Based on this discharging rule, analysing different possible cases, they finally reach at a contradiction to the initial assumption. The article is well written and the presentation is logically and mathematically sound. Hence, reading this article provides a delightful experience.
Reviewer: Sudev Naduvath (Thrissur)
MSC:
| 05C15 | Coloring of graphs and hypergraphs |
| 05C10 | Planar graphs; geometric and topological aspects of graph theory |
| 05C38 | Paths and cycles |
| 05C07 | Vertex degrees |
