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

DOI10.1016/J.DISC.2015.08.026zbMATH Open1322.05055arXiv1412.2624OpenAlexW1942599361MaRDI QIDQ501082FDOQ501082

Authors: Julien Bensmail, A. Lagoutte, Petru Valicov 

Publication date: 8 October 2015

Published in: Discrete Mathematics (Search for Journal in Brave)

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.

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

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

zbMATH Keywords

complexitybipartite graphsstrong edge-coloring

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Cites Work

• Incidence and strong edge colorings of graphs
• A bound on the strong chromatic index of a graph
• Title not available (Why is that?)
• Graph Bipartization and via minimization
• The strong chromatic index of a cubic graph is at most 10
• Strong edge-coloring of graphs with maximum degree 4 using 22 colors
• Induced matchings in cubic graphs
• On induced matchings
• A note on the strong chromatic index of bipartite graphs
• Title not available (Why is that?)

Cited In (16)

• On maximum \(k\)-edge-colorable subgraphs of bipartite graphs
• \(\Theta \)-graphs of partial cubes and strong edge colorings
• A problem for strong vertex colouring of graphs
• On incidence choosability of cubic graphs
• Destroying Bicolored $P_3$s by Deleting Few Edges
• Factors of \(r\)-partite graphs and bounds for the strong chromatic number.
• A note on edge coloring of graphs.
• Strong edge coloring sparse 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
• 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)