We show that f(x)=⌊[Formulla presented]x⌋ 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)≤[Formulla presented]α(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.
Bounded clique cover of some sparse graphs / Munaro, Andrea. - In: DISCRETE MATHEMATICS. - ISSN 0012-365X. - 340:9(2017), pp. 2208-2216. [10.1016/j.disc.2017.04.004]
Bounded clique cover of some sparse graphs
Andrea Munaro
2017-01-01
Abstract
We show that f(x)=⌊[Formulla presented]x⌋ 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)≤[Formulla presented]α(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.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
