Bounded clique cover of some sparse graphs

DOI10.1016/J.DISC.2017.04.004zbMath1365.05161OpenAlexW2658744303MaRDI QIDQ2359963

Andrea Munaro

Publication date: 23 June 2017

Published in: Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://pureadmin.qub.ac.uk/ws/files/186487173/cliquecover.pdf

zbMATH Keywords

bounded degree graphsPTASclique cover\(\theta\)-bounded

Mathematics Subject Classification ID

Vertex degrees (05C07) Density (toughness, etc.) (05C42)

Related Items (4)

CPG graphs: some structural and hardness results ⋮ Triangle packings and transversals of some \(K_{4}\)-free graphs ⋮ Some problems on induced subgraphs ⋮ Revising Johnson's table for the 21st century

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Complements of nearly perfect graphs
• Independent sets and matchings in subcubic graphs
• The chromatic gap and its extremes
• Independence in graphs with maximum degree four
• Partition into cliques for cubic graphs: Planar case, complexity and approximation
• The independence number in graphs of maximum degree three
• Linear chromatic bounds for a subfamily of \(3K_{1}\)-free graphs
• A partial k-arboretum of graphs with bounded treewidth
• Finding independent sets in \(K_4\)-free 4-regular connected graphs
• Critical graphs with connected complements
• Complexity of approximating bounded variants of optimization problems
• Independence and matching number in graphs with maximum degree 4
• Approximation algorithms for NP-complete problems on planar graphs
• The Complexity of Combinatorial Optimization Problems on d‐Dimensional Boxes

This page was built for publication: Bounded clique cover of some sparse graphs