Neighbour sum distinguishing total colourings via the Combinatorial Nullstellensatz

详细信息    查看全文

• 作者：Jakub Przybyło ; ^{jakubprz@agh.edu.pl" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Total neighbour sum distinguishing number ; List total colouring ; Combinatorial Nullstellensatz ; Adjacent strong chromatic index ; Neighbour sum distinguishing index ; 1&ndash ; 2-Conjecture ; Graph labelling
• 刊名：Discrete Applied Mathematics
• 出版年：2016
• 出版时间：31 March 2016
• 年：2016
• 卷：202
• 期：Complete
• 页码：163-173
• 全文大小：401 K

文摘

Consider a simple graph G=(V,E)$G=(V,E)$ and its (proper) total colouring c$c$ with elements of the set {1,2,…,k}$\{1,2,\dots ,k\}$. We say that c$c$ is neighbour sum distinguishing   if for every edge uv∈E$uv\in E$, the sums of colours met by u$u$ and v$v$ differ, i.e., c(u)+∑_e∋uc(e)≠c(v)+∑_e∋vc(e)$c\left(u\right)+{\sum }_{e\ni u}c\left(e\right)\ne c\left(v\right)+{\sum }_{e\ni v}c\left(e\right)$. The least k$k$ guaranteeing the existence of such a colouring is denoted χ″_∑(G)${\chi ″}_{\sum }\left(G\right)$. We investigate a daring conjecture presuming that χ″_∑(G)≤Δ(G)+3${\chi ″}_{\sum }\left(G\right)\le \Delta \left(G\right)+3$ for every graph G$G$, a seemingly demanding problem if confronted with up-to-date progress in research on the Total Colouring Conjecture itself.

We note that ${\chi ″}_{\sum }\left(G\right)\le \Delta \left(G\right)+2\mathrm{col}\left(G\right)-1$ and apply Combinatorial Nullstellensatz to prove a stronger bound: ${\chi ″}_{\sum }\left(G\right)\le \Delta \left(G\right)+\lceil \frac{5}{3}\mathrm{col}\left(G\right)\rceil$. This imply an upper bound of the form χ″_∑(G)≤Δ(G)+const${\chi ″}_{\sum }\left(G\right)\le \Delta \left(G\right)+const$. for many classes of graphs with unbounded maximum degree. In particular we obtain χ″_∑(G)≤Δ(G)+10${\chi ″}_{\sum }\left(G\right)\le \Delta \left(G\right)+10$ for planar graphs.

In fact we show that identical bounds also hold if we use any set of k$k$ real numbers instead of {1,2,…,k}$\{1,2,\dots ,k\}$ as edge colours, and moreover the same is true in list versions of the both concepts.