On incidence choosability of cubic graphs

DOI10.1016/J.DISC.2019.03.004zbMATH Open1414.05118arXiv1804.06036OpenAlexW2964184200MaRDI QIDQ1999751FDOQ1999751

Boram Park, Sungsik Kang

Publication date: 27 June 2019

Published in: Discrete Mathematics (Search for Journal in Brave)

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.

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

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

zbMATH Keywords

cubic graphincidence coloringstrong edge coloringincidence choosability

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Cites Work

• Title not available (Why is that?)
• Incidence and strong edge colorings of graphs
• Title not available (Why is that?)
• Some results on the incidence coloring number of a graph
• On incidence coloring and star arboricity of graphs
• On incidence coloring for some cubic graphs
• The star arboricity of graphs
• The incidence coloring conjecture for graphs of maximum degree 3
• The incidence chromatic number of toroidal grids
• On incidence coloring conjecture in Cartesian products of graphs
• The strong equitable vertex 2-arboricity of complete bipartite and tripartite graphs
• A note on the strong chromatic index of bipartite graphs
• Invalid proofs on incidence coloring
• Strong Chromatic Index of Chordless Graphs
• Strong edge-coloring of \((3, \varDelta)\)-bipartite graphs
• The strong chromatic index of \((3,\Delta)\)-bipartite graphs
• On incidence coloring of complete multipartite and semicubic bipartite graphs
• NP-completeness of 4-incidence colorability of semi-cubic graphs
• Interval incidence coloring of subcubic graphs
• Incidence coloring of pseudo-Halin graphs
• Incidence choosability of graphs
• Note on incidence chromatic number of subquartic graphs

Cited In (3)

• Incidence choosability of graphs
• On incidence coloring for some cubic graphs
• 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)