Language:   Search:   Contact
Zentralblatt MATH has released its new interface!
For an improved author identification, see the new author database of ZBMATH.

# Simple Search

Query:
Enter a query and click »Search«...
Format:
Display: entries per page entries
Zbl 1197.05125
Czerwiński, Sebastian; Grytczuk, Jarosław; Ẓelazny, Wiktor
Lucky labelings of graphs.
(English)
[J] Inf. Process. Lett. 109, No. 18, 1078-1081 (2009). ISSN 0020-0190

Summary: Suppose the vertices of a graph $G$ were labeled arbitrarily by positive integers, and let $S(v)$ denote the sum of labels over all neighbors of vertex $v$. A labeling is lucky if the function $S$ is a proper coloring of $G$, that is, if we have $S(u)\neq S(v)$ whenever $u$ and $v$ are adjacent. The least integer $k$ for which a graph $G$ has a lucky labeling from the set $\{1,2,\cdots ,k\}$ is the lucky number of $G$, denoted by $\eta (G)$.\par Using algebraic methods we prove that $\eta (G)\leqslant k+1$ for every bipartite graph $G$ whose edges can be oriented so that the maximum out-degree of a vertex is at most $k$. In particular, we get that $\eta (T)\leqslant 2$ for every tree $T$, and $\eta (G)\leqslant 3$ for every bipartite planar graph $G$. By another technique we get a bound for the lucky number in terms of the acyclic chromatic number. This gives in particular that $\eta (G) \leqslant 100280245065$ for every planar graph $G$. Nevertheless we offer a provocative conjecture that $\eta (G) \leqslant \chi (G)$ for every graph $G$.
MSC 2000:
*05C78 Graph labelling

Keywords: combinatorial problems; lucky labeling; combinatorial nullstellensatz

Highlights
Master Server