کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
419849 683868 2011 8 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Partial characterizations of circle graphs
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Partial characterizations of circle graphs
چکیده انگلیسی

A circle graph   is the intersection graph of a family of chords on a circle. There is no known characterization of circle graphs by forbidden induced subgraphs that do not involve the notions of local equivalence or pivoting operations. We characterize circle graphs by a list of minimal forbidden induced subgraphs when the graph belongs to one of the following classes: linear domino graphs, P4P4-tidy graphs, and tree-cographs. We also completely characterize by minimal forbidden induced subgraphs the class of unit Helly circle graphs, which are those circle graphs having a model whose chords have all the same length, are pairwise different, and satisfy the Helly property.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 159, Issue 16, 28 September 2011, Pages 1699–1706
نویسندگان
, , , ,