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

Comment on this Item PDF MathML XML ASCII DVI PS BibTeX Online Ordering Article Journal

	Scientific prize winners of the ICM 2010
	Overhang
	Lie groups, physics and geometry. An introduction for physicists, engineers and chemists.

Simple Search

Zentralblatt MATH Berlin [Germany]