Campus Units

Mathematics

Document Type

Article

Publication Version

Accepted Manuscript

Publication Date

10-2017

Journal or Book Title

Discrete Mathematics

Volume

340

Issue

10

First Page

2538

Last Page

2549

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.

Comments

This article is 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.

Creative Commons License

Creative Commons Attribution-Noncommercial-No Derivative Works 4.0 License
This work is licensed under a Creative Commons Attribution-Noncommercial-No Derivative Works 4.0 License.

Copyright Owner

Elsevier B.V.

Language

en

File Format

application/pdf

Available for download on Sunday, July 01, 2018

Published Version

Share

COinS