Name
Abstract | ||
|---|---|---|
An additive coloring of a graph G is an assignment of positive integers $${\\{1,2,\\ldots ,k\\}}$$ { 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)}$$ ¿ ( G ) . We prove that $${\\eta (G) \\, \\leqslant \\, 468}$$ ¿ ( G ) ¿ 468 for every planar graph G. This improves a previous bound $${\\eta (G) \\, \\leqslant \\, 5544}$$ ¿ ( G ) ¿ 5544 due to Norin. The proof uses Combinatorial Nullstellensatz and the coloring number of planar hypergraphs. We also demonstrate that $${\\eta (G) \\, \\leqslant \\, 36}$$ ¿ ( G ) ¿ 36 for 3-colorable planar graphs, and $${\\eta (G) \\, \\leqslant \\, 4}$$ ¿ ( G ) ¿ 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}$$ r ¿ 2 there is an r-chromatic graph G r with no additive coloring by elements of any abelian group of order r. |
Year | DOI | Venue |
|---|---|---|
2014 | 10.1007/s00373-013-1331-y | Graphs and Combinatorics |
Keywords | Field | DocType |
Additive coloring, Planar graphs | Integer,Graph,Abelian group,Discrete mathematics,Combinatorics,Vertex (geometry),Constraint graph,Planar graph,Mathematics | Journal |
Volume | Issue | ISSN |
30 | 5 | 1435-5914 |
Citations | PageRank | References |
7 | 0.70 | 8 |
Authors | ||
6 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Tomasz Bartnicki | 1 | 65 | 7.31 |
| Bartlomiej Bosek | 2 | 66 | 14.26 |
| Sebastian Czerwiński | 3 | 26 | 4.15 |
| Jaroslaw Grytczuk | 4 | 124 | 16.45 |
| Grzegorz Matecki | 5 | 35 | 6.36 |
| Wiktor Żelazny | 6 | 15 | 2.40 |