On incidence choosability of cubic graphs

DOI10.1016/J.DISC.2019.03.004MaRDI QIDQ1999751zbMATH OpenOpenAlexFDO

Authors Sungsik Kang, Boram Park

Publication date 27 June 2019

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1804.06036

zbMATH Keywords

cubic graphincidence coloringstrong edge coloringincidence choosability

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

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 with $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 incidence $k$-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, attracted 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.

Recommendations

• Incidence choosability of graphs
• On incidence coloring for some cubic graphs
• The incidence coloring conjecture for graphs of maximum degree 3
• Some results on the incidence coloring number of a graph
• Cubic graphs with different incidence chromatic numbers

Cites work

• scientific article; zbMATH DE number 4187830 (Why is no real title available?)
• A note on the strong chromatic index of bipartite graphs
• Graph theory with applications
• Incidence and strong edge colorings of graphs
• Incidence choosability of graphs
• Incidence coloring of pseudo-Halin graphs
• Interval incidence coloring of subcubic graphs
• Invalid proofs on incidence coloring
• NP-completeness of 4-incidence colorability of semi-cubic graphs
• Note on incidence chromatic number of subquartic graphs
• On incidence coloring and star arboricity of graphs
• On incidence coloring conjecture in Cartesian products of graphs
• On incidence coloring for some cubic graphs
• On incidence coloring of complete multipartite and semicubic bipartite graphs
• Some results on the incidence coloring number of a graph
• Strong chromatic index of chordless graphs
• Strong edge-coloring of \((3, \varDelta)\)-bipartite graphs
• The incidence chromatic number of toroidal grids
• The incidence coloring conjecture for graphs of maximum degree 3
• The star arboricity of graphs
• The strong chromatic index of \((3,\Delta)\)-bipartite graphs

Cited in

(5)

• Incidence choosability of graphs
• Some results on the incidence coloring number of a graph
• On incidence coloring for some cubic graphs
• Cubic graphs with different incidence chromatic numbers
• List strong edge-colorings of sparse graphs

This page was built for publication: On incidence choosability of cubic graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1999751)