2018/06/19 by Mingfang Huang, Huang, Mingfang, Michael Santana +3 · 10 citations
Computer Science · Mathematics · #1-planar graph #Advanced Graph Theory Research #Brooks' theorem #Chordal graph #Combinatorics #Combinatorics (math.CO) #Complete coloring #Conjecture #Degree (music) #Delta #Discrete mathematics #Edge coloring #FOS: Mathematics #Fractional coloring #Graph #Graph Labeling and Dimension Problems #Graph coloring #Graph power #Limits and Structures in Graph Theory #Line graph #Mathematical analysis #Mathematics #Physics #Upper and lower bounds #math.CO
paper · pdf · doi:10.48550/arxiv.1806.07012
published in arXiv (Cornell University) (Cornell University)
arxiv created 2018/06/19 · openalex publication_date 2018/06/19 · arxiv updated 2018/06/20 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/08
A strong edge-coloring of a graph G is a coloring of the edges such that every color class induces a matching in G. The strong chromatic index of a graph is the minimum number of colors needed in a strong edge-coloring of the graph. In 1985, Erdős and Nešetřil conjectured that every graph with maximum degree Δ has a strong edge-coloring using at most (5)/(4)Δ2 colors if Δ is even, and at most (5)/(4)Δ2 - (1)/(2)Δ+ (1)/(4) if Δ is odd. Despite recent progress for large Δ by using an iterative probabilistic argument, the only nontrivial case of the conjecture that has been verified is when Δ= 3, leaving the need for new approaches to verify the conjecture for any Δ≥ 4. In this paper, we apply some ideas used in previous results to an upper bound of 21 for graphs with maximum degree 4, which improves a previous bound due to Cranston in 2006 and moves closer to the conjectured upper bound of 20.