کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4648651 1342422 2011 10 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Two forbidden induced subgraphs and well-quasi-ordering
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
Two forbidden induced subgraphs and well-quasi-ordering
چکیده انگلیسی

It is known that a class of graphs defined by a single forbidden induced subgraph GG is well-quasi-ordered by the induced subgraph relation if and only if GG is an induced subgraph of P4P4. However, very little is known about well-quasi-ordered classes of graphs defined by more than one forbidden induced subgraph. We conjecture that for any natural number kk, there are finitely many minimal classes of graphs defined by kk forbidden induced subgraphs which are not well-quasi-ordered by the induced subgraph relation and prove the conjecture for k=2k=2. We explicitly reveal many of the minimal classes defined by two forbidden induced subgraphs which are not well-quasi-ordered and many of those which are well-quasi-ordered by the induced subgraph relation.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 311, Issue 16, 28 August 2011, Pages 1813–1822
نویسندگان
, ,