On incidence choosability of cubic graphs

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.