Injective choosability of subcubic planar graphs with girth 6
Date
Authors
Major Professor
Advisor
Committee Member
Journal Title
Journal ISSN
Volume Title
Publisher
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.
Series Number
Journal Issue
Is Version Of
Versions
Series
Academic or Administrative Unit
Type
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.