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


On incidence choosability of cubic graphs
Authors:Sungsik Kang  Boram Park
Abstract:An incidence of a graph G is a pair (u,e) where u is a vertex of G and e is an edge of G incident to u. Two incidences (u,e) and (v,f) of G are adjacent whenever (i) u=v, or (ii) e=f, or (iii) uv=e or uv=f. An incidencek-coloring of G is a mapping from the set of incidences of G to a set of k colors such that every two adjacent incidences receive distinct colors. The notion of incidence coloring has been introduced by Brualdi and Quinn Massey (1993) from a relation to strong edge coloring, and since then, has attracted a lot of attention by many authors.On a list version of incidence coloring, it was shown by Benmedjdoub et al. (2017) that every Hamiltonian cubic graph is incidence 6-choosable. In this paper, we show that every cubic (loopless) multigraph is incidence 6-choosable. As a direct consequence, it implies that the list strong chromatic index of a (2,3)-bipartite graph is at most 6, where a (2,3)-bipartite graph is a bipartite graph such that one partite set has maximum degree at most 2 and the other partite set has maximum degree at most 3.
Keywords:Corresponding author.  Incidence coloring  Incidence choosability  Strong edge coloring  Cubic graph
本文献已被 ScienceDirect 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

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