Injective choosability of subcubic planar graphs with girth 6 |
| |
Authors: | Boris Brimkov Jennifer Edmond Robert Lazar Bernard Lidický Kacy Messerschmidt Shanise Walker |
| |
Affiliation: | 1. Department of Computational and Applied Mathematics, Rice University, USA;2. Mathematics Department, Syracuse University, USA;3. Department of Mathematics, Iowa State University, USA |
| |
Abstract: | An injective coloring of a graph is an assignment of colors to the vertices of so that any two vertices with a common neighbor have distinct colors. A graph is injectively -choosable if for any list assignment , where for all , has an injective -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: | Planar graph Injective coloring Subcubic |
本文献已被 ScienceDirect 等数据库收录! |
|