Skip to main content
Article
Additive list coloring of planar graphs with given girth
Discussiones Mathematicae Graph Theory (2018)
  • Axel Brandt, Northern Kentucky University
  • Sogol Jahanbekam, San Jose State University
  • Jennifer Diemunsch, Saint Vincent College
Abstract
An additive coloring of a graph G is a labeling of the vertices of G from {1,2,...,k} such that two adjacent vertices have distinct sums of labels on their neighbors. The least integer k for which a graph G has an additive coloring is called the additive coloring number of G, denoted \luck(G). Additive coloring is also studied under the names lucky labeling and open distinguishing. In this paper, we improve the current bounds on the additive coloring number for particular classes of graphs by proving results for a list version of additive coloring. We apply the discharging method and the Combinatorial Nullstellensatz to show that every planar graph G with girth at least 5 has \luck(G)≤ 19, and for girth at least 67, and 26\luck(G) is at most 9, 8, and 3, respectively. In 2009, Czerwi\acute{\mbox{n}}ski, Grytczuk, and \dot{\mbox{Z}}elazny conjectured that \luck(G) ≤ χ(G), where χ(G) is the chromatic number of G. Our result for the class of non-bipartite planar graphs of girth at least 26 is best possible and affirms the conjecture for this class of graphs.
Keywords
  • lucky labeling,
  • additive coloring,
  • reducible configuration,
  • discharging method,
  • Combinatorial Nullstellensatz
Publication Date
May 18, 2018
DOI
10.7151/dmgt.2156
Publisher Statement
This article is in press for the journal Discussiones Mathematicae Graph Theory and can also be found online at this link.
Citation Information
Axel Brandt, Sogol Jahanbekam and Jennifer Diemunsch. "Additive list coloring of planar graphs with given girth" Discussiones Mathematicae Graph Theory (2018) ISSN: 2083-5892
Available at: http://works.bepress.com/sogol-jahanbekam/5/