Strong edge-coloring of (3,Δ)-bipartite graphs

A strong edge-coloring of a graph G 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Δ-edge-colo...

Full description

Saved in:
Bibliographic Details
Published in:Discrete mathematics 2016-01, Vol.339 (1), p.391-398
Main Authors: Bensmail, Julien, Lagoutte, Aurélie, Valicov, Petru
Format: Article
Language:English
Subjects:
Bipartite graphs
Complexity
Computer Science
Discrete Mathematics
Strong edge-coloring
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:A strong edge-coloring of a graph G 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Δ-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.
ISSN:0012-365X
1872-681X
DOI:10.1016/j.disc.2015.08.026