کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4652853 1632603 2007 7 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Polar cographs
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
Polar cographs
چکیده انگلیسی

A graph is (s, k)-polar if there exists a partition A, B of its vertex set such that A induces a complete s-partite graph and B a disjoint union of at most k cliques. Recognizing a polar graph is known to be NP-complete. Here we consider the class of polar graphs which are also cographs. We provide polynomial time algorithms and forbidden subgraphs characterizations for problems related to polar cographs.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Electronic Notes in Discrete Mathematics - Volume 28, 1 March 2007, Pages 317-323