Strong edge-colouring and induced matchings
From MaRDI portal
Publication:2445264
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
computational complexity; planar graphs; outerplanar graphs; induced matching; strong edge-colouring
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