Bounded clique cover of some sparse graphs

Research output: Contribution to journalArticlepeer-review

6 Citations (Scopus)
297 Downloads (Pure)

Abstract

We show that f(x)=⌊32x⌋ is a θ-bounding function for the class of subcubic graphs and that it is best possible. This generalizes a result by Henning et al. (2012), who showed that θ(G)≤32α(G) for any subcubic triangle-free graph G. Moreover, we provide a θ-bounding function for the class of K4-free graphs with maximum degree at most 4. Finally, we study the problem Clique Cover for subclasses of planar graphs and graphs with bounded maximum degree: in particular, answering a question of Cerioli et al. (2008), we show it admits a PTAS for planar graphs.
Original languageEnglish
Pages (from-to)2208-2216
Number of pages9
JournalDiscrete Mathematics
Volume340
Issue number9
Early online date21 Jun 2017
DOIs
Publication statusPublished - Sept 2017

Keywords

  • Bounded degree graphs
  • Clique cover
  • PTAS
  • θ-bounded

Fingerprint

Dive into the research topics of 'Bounded clique cover of some sparse graphs'. Together they form a unique fingerprint.

Cite this