Strong edge-colouring and induced matchings

DOI10.1016/j.ipl.2013.07.026zbMath1284.68281MaRDI 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 complexity; planar graphs; outerplanar graphs; induced matching; strong edge-colouring

Mathematics Subject Classification ID

05C10: Planar graphs; geometric and topological aspects of graph theory

05C15: Coloring of graphs and hypergraphs

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

Related Items

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