Injective choosability of subcubic planar graphs with girth 6

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 coloring...

Full description

Saved in:
Bibliographic Details
Published in:Discrete mathematics 2017-10, Vol.340 (10), p.2538-2549
Main Authors: Brimkov, Boris, Edmond, Jennifer, Lazar, Robert, Lidický, Bernard, Messerschmidt, Kacy, Walker, Shanise
Format: Article
Language:English
Subjects:
Injective coloring
Planar graph
Subcubic
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:0012-365X
1872-681X
DOI:10.1016/j.disc.2017.05.014