Neighbor Sum (Set) Distinguishing Total Choosability of d-Degenerate Graphs

详细信息    查看全文

• 作者：Jingjing Yao ; Xiaowei Yu ; Guanghui Wang ; Changqing Xu
• 刊名：Graphs and Combinatorics
• 出版年：2016
• 出版时间：July 2016
• 年：2016
• 卷：32
• 期：4
• 页码：1611-1620
• 全文大小：425 KB
• 刊物类别：Mathematics and Statistics
• 刊物主题：Mathematics
  Combinatorics
  Engineering Design
  
• 出版者：Springer Japan
• ISSN：1435-5914
• 卷排序：32

文摘

Let \(G=(V,E)\) be a graph with maximum degree \(\varDelta (G)\) and \(\phi :V\cup E\rightarrow \{1,2,\ldots ,k\}\) be a proper total coloring of the graph G. Let S(v) denote the set of the color on vertex v and the colors on the edges incident with v. Let f(v) denote the sum of the color on vertex v and the colors on the edges incident with v. The proper total coloring \(\phi \) is called neighbor set distinguishing or adjacent vertex distinguishing if \(S(u)\ne S(v)\) for each edge \(uv\in E(G)\). We say that \(\phi \) is neighbor sum distinguishing if \(f(u)\ne f(v)\) for each edge \(uv\in E(G)\). In both problems the challenging conjectures presume that such colorings exist for any graph G if \(k\ge \varDelta (G)+3\). Ding et al. proved in both problems \(k\ge \varDelta (G)+2d\) is sufficient for d-degenerate graph G. In this paper, we improve this bound and prove that \(k\ge \varDelta (G)+d+1\) is sufficient for d-degenerate graph G with \(d\le 8\) and \(\varDelta (G)\ge 2d\) or \(d\ge 9\) and \(\varDelta (G)\ge \frac{5}{2}d-5\). In fact, we prove these results in their list versions. As a consequence, we obtain an upper bound of the form \(\varDelta (G)+C\) for some families of graphs, e.g. \(\varDelta (G)+6\) for planar graphs with \(\varDelta (G)\ge 10\). In particular, we therefore obtain that when \(\varDelta (G)\ge 4\) two conjectures we mentioned above hold for 2-degenerate graphs in their list versions.KeywordsNeighbor sum (set)  distinguishing total coloringAdjacent vertex distinguishing total coloringd-Degenerate graphList total coloringCombinatorial Nullstellensatz