Skip to main content
Article
Injective choosability of subcubic planar graphs with girth 6
Discrete Mathematics
  • Boris Brimkov, Rice University
  • Jennifer Edmond, Syracuse University
  • Robert Lazar, Iowa State University
  • Bernard Lidicky, Iowa State University
  • Kacy Messerschmidt, Iowa State University
  • Shanise Walker, Iowa State University
Document Type
Article
Publication Version
Accepted Manuscript
Publication Date
10-1-2017
DOI
10.1016/j.disc.2017.05.014
Abstract

An injective coloring of a graph G is an assignment of colors to the vertices of G so that any two vertices with a common neighbor have distinct colors. A graph G is injectively k-choosable if for any list assignment L, where |L(v)| ≥ k for all vV(G), G has an injective L-coloring. Injective colorings have applications in the theory of error-correcting codes and are closely related to other notions of colorability. In this paper, we show that subcubic planar graphs with girth at least 6 are injectively 5-choosable. This strengthens the result of Lužar, Škrekovski, and Tancer that subcubic planar graphs with girth at least 7 are injectively 5-colorable. Our result also improves several other results in particular cases.

Comments

This is a manuscript of an article published as Brimkov, Boris, Jennifer Edmond, Robert Lazar, Bernard Lidický, Kacy Messerschmidt, and Shanise Walker. "Injective choosability of subcubic planar graphs with girth 6." Discrete Mathematics 340, no. 10 (2017): 2538-2549. 10.1016/j.disc.2017.05.014 Posted with permission.

Creative Commons License
Creative Commons Attribution-NonCommercial-No Derivative Works 4.0 International
Copyright Owner
Elsevier B.V.
Language
en
File Format
application/pdf
Citation Information
Boris Brimkov, Jennifer Edmond, Robert Lazar, Bernard Lidicky, et al.. "Injective choosability of subcubic planar graphs with girth 6" Discrete Mathematics Vol. 340 Iss. 10 (2017) p. 2538 - 2549
Available at: http://works.bepress.com/bernard-lidicky/35/