Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4651223 | Discrete Mathematics | 2006 | 7 Pages |
Abstract
In 1985, Erdős and Neśetril conjectured that the strong edge-coloring number of a graph is bounded above by 54Δ2 when ΔΔ is even and 14(5Δ2-2Δ+1) when ΔΔ is odd. They gave a simple construction which requires this many colors. The conjecture has been verified for Δ⩽3Δ⩽3. For Δ=4Δ=4, the conjectured bound is 20. Previously, the best known upper bound was 23 due to Horak. In this paper we give an algorithm that uses at most 22 colors.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Daniel W. Cranston,