Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
5776887 | Discrete Mathematics | 2017 | 12 Pages |
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.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Boris Brimkov, Jennifer Edmond, Robert Lazar, Bernard Lidický, Kacy Messerschmidt, Shanise Walker,