Partition into cliques for cubic graphs: Planar case, complexity and approximation
From MaRDI portal
Publication:947111
DOI10.1016/j.dam.2007.10.015zbMath1144.05049OpenAlexW1985638002MaRDI QIDQ947111
C. A. J. Martinhon, T. O. Ferreira, Luérbio Faria, Fábio Protti, Márcia R. Cerioli, Bruce A. Reed
Publication date: 29 September 2008
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.dam.2007.10.015
Extremal problems in graph theory (05C35) Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)
Related Items (11)
Bounded clique cover of some sparse graphs ⋮ Art gallery problem with rook and queen vision ⋮ Corrigendum to ``Cycle transversals in perfect graphs and cographs ⋮ Computational Complexity of the $$r$$-visibility Guard Set Problem for Polyominoes ⋮ Structured proportional representation ⋮ On the tractability of finding disjoint clubs in a network ⋮ Oriented coloring in planar, bipartite, bounded degree 3 acyclic oriented graphs ⋮ A weakly robust PTAS for minimum clique partition in unit disk graphs ⋮ Covering a Graph with Clubs ⋮ On the tractability of covering a graph with 2-clubs ⋮ Revising Johnson's table for the 21st century
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Optimization, approximation, and complexity classes
- A still better performance guarantee for approximate graph coloring
- Some simplified NP-complete graph problems
- Planar Formulae and Their Uses
- The Complexity of Planar Counting Problems
- Free Bits, PCPs, and Nonapproximability---Towards Tight Results
- Approximating k-set cover and complementary graph coloring
- Paths, Trees, and Flowers
This page was built for publication: Partition into cliques for cubic graphs: Planar case, complexity and approximation
