Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4646831 | Discrete Mathematics | 2016 | 8 Pages |
Abstract
A strong edge-coloring of a graph GG is an assignment of colors to edges such that every color class induces a matching. We here focus on bipartite graphs whose one part is of maximum degree at most 3 and the other part is of maximum degree ΔΔ. For every such graph, we prove that a strong 4Δ4Δ-edge-coloring can always be obtained. Together with a result of Steger and Yu, this result confirms a conjecture of Faudree, Gyárfás, Schelp and Tuza for this class of graphs.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Julien Bensmail, Aurélie Lagoutte, Petru Valicov,