Injective choosability of subcubic planar graphs with girth 6

Thumbnail Image
Date
2017-10-01
Authors
Brimkov, Boris
Edmond, Jennifer
Lazar, Robert
Messerschmidt, Kacy
Walker, Shanise
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 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.

Series Number
Journal Issue
Is Version Of
Versions
Series
Academic or Administrative Unit
Type
article
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.

Rights Statement
Copyright
Sun Jan 01 00:00:00 UTC 2017
Funding
DOI
Supplemental Resources
Collections