کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
417980 681597 2016 9 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Classifying the clique-width of HH-free bipartite graphs
ترجمه فارسی عنوان
طبقه بندی عرض دسته نمودارهای دوبخشی بدون HH
کلمات کلیدی
دسته عرض؛ گراف دوبخشی؛ کلاس گراف
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی

Let  GG be a bipartite graph, and let  HH be a bipartite graph with a fixed bipartition (BH,WH)(BH,WH). We consider three different, natural ways of forbidding  HH as an induced subgraph in  GG. First, GG is HH-free if it does not contain  HH as an induced subgraph. Second, GG is strongly HH-free if no bipartition of  GG contains an induced copy of  HH in a way that respects the bipartition of  HH. Third, GG is weakly HH-free if  GG has at least one bipartition that does not contain an induced copy of  HH in a way that respects the bipartition of  HH. Lozin and Volz characterized all bipartite graphs  HH for which the class of strongly HH-free bipartite graphs has bounded clique-width. We extend their result by giving complete classifications for the other two variants of HH-freeness.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 200, 19 February 2016, Pages 43–51
نویسندگان
, ,