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 language | English |
---|---|
Pages (from-to) | 2208-2216 |
Number of pages | 9 |
Journal | Discrete Mathematics |
Volume | 340 |
Issue number | 9 |
Early online date | 21 Jun 2017 |
DOIs | |
Publication status | Published - Sept 2017 |
Keywords
- Bounded degree graphs
- Clique cover
- PTAS
- θ-bounded