首页 | 本学科首页   官方微博 | 高级检索  
     


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 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.
Keywords:Planar graph  Injective coloring  Subcubic
本文献已被 ScienceDirect 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号