19-25 June 2011
Bled, Slovenia
Europe/Ljubljana timezone
Home > Timetable > Contribution details

Neighbour distinguishing edge colourings via the Combinatorial Nullstellensatz

Presented by Jakub PRZYBYłO
Type: Oral presentation
Track: Coloring of Graphs


Consider a simple graph $G=(V,E)$ and its \emph{proper} edge colouring $c$ with the elements of the set $\{1,2,\ldots,k\}$ (or any other $k$-element set of real numbers). We say that $c$ is \emph{neighbour sum distinguishing} if $\sum_{w\in N_G(v)}c(wv)\neq \sum_{w\in N_G(u)}c(wu)$ for every edge $uv\in E$. We show that such colouring exists for any graph $G$ containing no isolated edges if only $k\geq 2\Delta(G)+{\rm col}(G)-1$ or $k\geq \Delta(G)+3{\rm col}(G)-4$. The algorithmic proofs of these two facts are based on the Combinatorial Nullstellensatz and inspired by a recent paper of Wong and Zhu [\emph{Antimagic labelling of vertex weighted graphs}, J. Graph Theory, to appear]. As a consequence, the same number of colours is also sufficient in the well known corresponding problem, where instead of the sums, we wish to distinguish the \emph{sets} of colours met by adjacent vertices. In fact we consider list versions of the both concepts and prove our assertions in this more general setting. The second bound implies, e.g., that $k=\Delta(G)+14$ is sufficient for all planar grphs. On the other hand, the corresponding conjectures by Zhang et al. and Flandrin et al. suggest that $k=\Delta(G)+2$ should suffice for all connected graphs of order at least three, except for $C_5$.


Location: Bled, Slovenia
Address: Best Western Hotel Kompas Bled

Primary authors