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

DOI10.1016/J.DISC.2015.08.026MaRDI QIDQ501082zbMATH OpenOpenAlexFDO

Authors Julien Bensmail, A. Lagoutte, Petru Valicov

Publication date 8 October 2015

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1412.2624

zbMATH Keywords

complexitybipartite graphsstrong edge-coloring

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Abstract: 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 $Delta$. For every such graph, we prove that a strong $4Delta$-edge-coloring can always be obtained. Together with a result of Steger and Yu, this result confirms a conjecture of Faudree, Gy'arf'as, Schelp and Tuza for this class of graphs.

Recommendations

• The strong chromatic index of \((3,\Delta)\)-bipartite graphs
• A note on the strong chromatic index of bipartite graphs
• Strong edge colorings of uniform graphs
• Strong edge coloring sparse graphs
• Strong edge-coloring of cubic bipartite graphs: a counterexample

Cites work

• scientific article; zbMATH DE number 3851125 (Why is no real title available?)
• scientific article; zbMATH DE number 4187830 (Why is no real title available?)
• A bound on the strong chromatic index of a graph
• A note on the strong chromatic index of bipartite graphs
• Graph Bipartization and via minimization
• Incidence and strong edge colorings of graphs
• Induced matchings in cubic graphs
• On induced matchings
• Strong edge-coloring of graphs with maximum degree 4 using 22 colors
• The strong chromatic index of a cubic graph is at most 10

Cited in

(17)

• On maximum \(k\)-edge-colorable subgraphs of bipartite graphs
• \(\Theta \)-graphs of partial cubes and strong edge colorings
• On incidence choosability of cubic graphs
• A problem for strong vertex colouring of graphs
• Destroying Bicolored $P_3$s by Deleting Few Edges
• Factors of \(r\)-partite graphs and bounds for the strong chromatic number.
• Strong edge coloring sparse graphs
• A note on edge coloring of graphs.
• A note on the strong chromatic index of bipartite graphs
• Strong edge-coloring of cubic bipartite graphs: a counterexample
• The inclusion-free edge-colorings of \((3, \varDelta)\)-bipartite graphs
• List strong edge-colorings of sparse graphs
• Destroying bicolored \(P_3\)s by deleting few edges
• Hypergraph incidence coloring
• Recent progress on strong edge-coloring of graphs
• The strong chromatic index of \((3,\Delta)\)-bipartite graphs
• Strong edge colorings of uniform graphs

This page was built for publication: Strong edge-coloring of \((3, \varDelta)\)-bipartite graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q501082)