Additive colorings of planar graphs

Details Additive colorings of planar graphs Additive colorings of planar graphs

2012-02-03

arxiv.org/abs/1202.0667v2

Mathematics

Combinatorics

Scientific paper

An \emph{additive coloring} of a graph $G$ is an assignment of positive integers $\{1,2,...,k\}$ to the vertices of $G$ such that for every two adjacent vertices the sums of numbers assigned to their neighbors are different. The minimum number $k$ for which there exists an additive coloring of $G$ is denoted by $\eta (G)$. We prove that $\eta (G)\leqslant 468$ for every planar graph $G$. This improves a previous bound $\eta (G)\leqslant 5544$ due to Norin. The proof uses Combinatorial Nullstellensatz and coloring number of planar hypergrahs. We also demonstrate that $\eta (G)\leqslant 36$ for 3-colorable planar graphs, and $\eta (G)\leqslant 4$ for every planar graph of girth at least 13. In a group theoretic version of the problem we show that for each $r\geqslant 2$ there is an $r$-chromatic graph $G_{r}$ with no additive coloring by elements of any Abelian group of order $r$.

Affiliated with

Also associated with

No associations

Rating

Additive colorings of planar graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Additive colorings of planar graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Additive colorings of planar graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-4544