Neighbor Distinguishing Edge Colorings via the Combinatorial Nullstellensatz
Author:
- Jakub PrzybyłoJPJakub Przybyło
- 1 January 2013
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Discrete Mathematics
- Vol. 27 (3) , 1313-1322
Abstract
Consider a simple graph $G=(V,E)$ and its proper edge coloring $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 neighbor 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 a coloring exists for any graph $G$ containing no isolated edges if $k\geq 2\Delta(G)+{\rm col}(G)-1$. The proof of this fact is based on iterative applications of the Combinatorial Nullstellensatz. As a consequence, the same number of colors is also sufficient in the well-known corresponding problem, where instead of the sums, we wish to distinguish the sets of colors met by adjacent vertices. In fact we consider list versions of both concepts and prove our assertion in this more general setting.
Keywords
This publication has 12 references indexed in Scilit:
- Total weight choosability of graphsJournal of Graph Theory, 2010
- Vertex-coloring edge-weightings: Towards the 1-2-3-conjectureJournal of Combinatorial Theory, Series B, 2010
- Degree constrained subgraphsDiscrete Applied Mathematics, 2008
- Vertex-Colouring Edge-WeightingsCombinatorica, 2007
- Adjacent Vertex Distinguishing Edge‐ColoringsSIAM Journal on Discrete Mathematics, 2007
- r-Strong edge colorings of graphsDiscrete Mathematics, 2006
- is a bound on the adjacent vertex distinguishing edge chromatic numberJournal of Combinatorial Theory, Series B, 2005
- Edge weights and vertex coloursJournal of Combinatorial Theory, Series B, 2004
- Combinatorial NullstellensatzCombinatorics, Probability and Computing, 1999
- The number of edge 3-colorings of a planar cubic graph as a permanentDiscrete Mathematics, 1974