Strong edge-colouring and induced matchings
From MaRDI portal
Publication:2445264
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
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