pith. machine review for the scientific record. sign in

arxiv: 1809.01805 · v2 · submitted 2018-09-06 · 🧮 math.CO

Recognition: unknown

Strong list-chromatic index of subcubic graphs

Authors on Pith no claims yet
classification 🧮 math.CO
keywords strongedge-coloringgraphindexeverylist-chromaticsubcubicdegree
0
0 comments X
read the original abstract

A strong $k$-edge-coloring of a graph G is an edge-coloring with $k$ colors in which every color class is an induced matching. The strong chromatic index of $G$, denoted by $\chi'_{s}(G)$, is the minimum $k$ for which $G$ has a strong $k$-edge-coloring. In 1985, Erd\H{o}s and Ne\v{s}et\v{r}il conjectured that $\chi'_{s}(G)\leq\frac{5}{4}\Delta(G)^2$, where $\Delta(G)$ is the maximum degree of $G$. When $G$ is a graph with maximum degree at most 3, the conjecture was verified independently by Andersen and Hor\'{a}k, Qing, and Trotter. In this paper, we consider the list version of strong edge-coloring. In particular, we show that every subcubic graph has strong list-chromatic index at most 11 and every planar subcubic graph has strong list-chromatic index at most 10.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.