کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
5776759 | 1413640 | 2017 | 9 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Bounded clique cover of some sparse graphs
ترجمه فارسی عنوان
پوشش کلاسی محدود برخی از نمودارهای ناهموار
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
چکیده انگلیسی
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.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 340, Issue 9, September 2017, Pages 2208-2216
Journal: Discrete Mathematics - Volume 340, Issue 9, September 2017, Pages 2208-2216
نویسندگان
Andrea Munaro,