Article
Injective choosability of subcubic planar graphs with girth 6
Discrete Mathematics
Document Type
Article
Disciplines
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 v ∈ V(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.
Creative Commons License
Creative Commons Attribution-NonCommercial-No Derivative Works 4.0 International
Copyright Owner
Elsevier B.V.
Copyright Date
2017
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/
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.