The adjacent vertex distinguishing total coloring of planar graphs without adjacent 4-cycles

详细信息    查看全文

• 作者：Lin Sun ; Xiaohan Cheng ; Jianliang Wu
• 关键词：Planar graph ; Adjacent vertex distinguishing total coloring ; Combinatorial Nullstellensatz ; Discharging method
• 刊名：Journal of Combinatorial Optimization
• 出版年：2017
• 出版时间：February 2017
• 年：2017
• 卷：33
• 期：2
• 页码：779-790
• 全文大小：
• 刊物类别：Mathematics and Statistics
• 刊物主题：Combinatorics; Convex and Discrete Geometry; Mathematical Modeling and Industrial Mathematics; Theory of Computation; Optimization; Operation Research/Decision Theory;
• 出版者：Springer US
• ISSN：1573-2886
• 卷排序：33

文摘

A total [k]-coloring of a graph G is a mapping \(\phi \): \(V(G)\cup E(G)\rightarrow [k]=\{1, 2,\ldots , k\}\) such that no two adjacent or incident elements in \(V(G)\cup E(G)\) receive the same color. In a total [k]-coloring \(\phi \) of G, let \(C_{\phi }(v)\) denote the set of colors of the edges incident to v and the color of v. If for each edge uv, \(C_{\phi }(u)\ne C_{\phi }(v)\), we call such a total [k]-coloring an adjacent vertex distinguishing total coloring of G. \(\chi ''_{a}(G)\) denotes the smallest value k in such a coloring of G. In this paper, by using the Combinatorial Nullstellensatz and the discharging method, we prove that if a planar graph G with maximum degree \(\Delta \ge 8\) contains no adjacent 4-cycles, then \(\chi ''_{a}(G)\le \Delta +3\).