Strong edge-colouring and induced matchings

DOI10.1016/J.IPL.2013.07.026MaRDI QIDQ2445264zbMATH OpenOpenAlexFDO

Authors Hervé Hocquard, Pascal Ochem, Petru Valicov

Publication date 14 April 2014

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ipl.2013.07.026

zbMATH Keywords

computational complexityinduced matchingouterplanar graphsplanar graphsstrong edge-colouring

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• Strong edge colorings of graphs
• Incidence and strong edge colorings of graphs
• From edge-coloring to strong edge-coloring
• scientific article; zbMATH DE number 3851125
• scientific article; zbMATH DE number 1267271
• r-strong edge colorings of graphs
• d-strong edge colorings of graphs
• Rainbow matchings in strongly edge-colored graphs
• Strong edge-coloring of planar graphs
• Strong edge-coloring of planar graphs

Cites work

• A polynomial time algorithm for strong edge coloring of partial \(k\)-trees
• A special planar satisfiability problem and a consequence of its NP- completeness
• scientific article; zbMATH DE number 3851125 (Why is no real title available?)
• scientific article; zbMATH DE number 4187830 (Why is no real title available?)
• Induced matchings
• Induced matchings in bipartite graphs
• On maximum induced matchings in bipartite graphs
• On the approximability of the maximum induced matching problem
• On the computational complexity of strong edge coloring
• Some simplified NP-complete graph problems

Cited in

(20)

• Complexity and algorithms for injective edge-coloring in graphs
• A characterization of well-indumatchable graphs having girth greater than seven
• On the strong chromatic index and maximum induced matching of tree-cographs, permutation graphs and chordal bipartite graphs
• Strong chromatic index of K₄-minor free graphs
• Bounds and complexity results for strong edge colouring of subcubic graphs
• Further results on strong edge-colourings in outerplanar graphs
• Strong edge coloring sparse graphs
• Semistrong edge coloring of graphs
• Strong chromatic index of planar graphs with large girth
• On the complexity of the flow coloring problem
• Between Proper and Strong Edge-Colorings of Subcubic Graphs
• Well-indumatched Trees and Graphs of Bounded Girth
• Between proper and strong edge‐colorings of subcubic graphs
• Strong incidence coloring of outerplanar graphs
• A note on strong edge-coloring of claw-free cubic graphs
• Strong edge-coloring of some sparse graphs
• Revisiting semistrong edge‐coloring of graphs
• Strong Edge Coloring of Outerplane Graphs with Independent Crossings
• On semistrong edge-colorings of outerplanar graphs
• The strong chromatic index of 1-planar graphs

This page was built for publication: Strong edge-colouring and induced matchings

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