Logo image
Se connecter
Strong edge-coloring of (3,Δ)-bipartite graphs
Article de revue   Avec comité de lecture

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

Julien Bensmail, Aurélie Lagoutte et Petru Valicov
Discrete mathematics, Vol.339(1), pp.391-398
06/01/2016

Résumé

Bipartite graphs Complexity Strong edge-coloring
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.

Indicateurs

1 Consultations de la notice

Détails

Logo image