Bounded clique cover of some sparse graphs

DOI10.1016/J.DISC.2017.04.004MaRDI QIDQ2359963zbMATH OpenOpenAlexFDO

Authors 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

\(\theta\)-boundedbounded degree graphsclique coverPTAS

Mathematics Subject Classification ID

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

Recommendations

• Covering the cliques of a graph with vertices
• Local clique covering of claw-free graphs
• A new upper bound for the clique cover number with applications
• On maximum \(P_3\)-packing in claw-free subcubic graphs
• Clique covering of graphs

Cites work

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

Cited in

(6)

• Some problems on induced subgraphs
• Revising Johnson's table for the 21st century
• Triangle packings and transversals of some \(K_{4}\)-free graphs
• scientific article; zbMATH DE number 1286502 (Why is no real title available?)
• Improved sparse covers for graphs excluding a fixed minor
• CPG graphs: some structural and hardness results

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2359963)