Strong edge-colouring and induced matchings

DOI10.1016/j.ipl.2013.07.026zbMath1284.68281OpenAlexW2086668882MaRDI QIDQ2445264

Petru Valicov, Pascal Ochem, Hervé Hocquard

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 complexityplanar graphsouterplanar graphsinduced matchingstrong 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)

Related Items (11)

Strong edge coloring sparse graphs ⋮ A characterization of well-indumatchable graphs having girth greater than seven ⋮ Strong chromatic index of \(K_4\)-minor free graphs ⋮ Strong incidence coloring of outerplanar graphs ⋮ A note on strong edge-coloring of claw-free cubic graphs ⋮ Unnamed Item ⋮ Strong chromatic index of planar graphs with large girth ⋮ Well-indumatched Trees and Graphs of Bounded Girth ⋮ On the complexity of the flow coloring problem ⋮ Complexity and algorithms for injective edge-coloring in graphs ⋮ Maximal Induced Matchings in Triangle-Free Graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Induced matchings in bipartite graphs
• Some simplified NP-complete graph problems
• Induced matchings
• A special planar satisfiability problem and a consequence of its NP- completeness
• On the computational complexity of strong edge coloring
• On the approximability of the maximum induced matching problem
• On maximum induced matchings in bipartite graphs
• A polynomial time algorithm for strong edge coloring of partial \(k\)-trees

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