کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
433898 689648 2016 13 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Hierarchical complexity of 2-clique-colouring weakly chordal graphs and perfect graphs having cliques of size at least 3
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Hierarchical complexity of 2-clique-colouring weakly chordal graphs and perfect graphs having cliques of size at least 3
چکیده انگلیسی

A clique of a graph is a maximal set of vertices of size at least 2 that induces a complete graph. A k-clique-colouring of a graph is a colouring of the vertices with at most k   colours such that no clique is monochromatic. Défossez proved that the 2-clique-colouring of perfect graphs is a Σ2P-complete problem (Défossez (2009) [4]). We strengthen this result by showing that it is still Σ2P-complete for weakly chordal graphs. We then determine a hierarchy of nested subclasses of weakly chordal graphs whereby each graph class is in a distinct complexity class, namely Σ2P-complete, NPNP-complete, and PP. We solve an open problem posed by Kratochvíl and Tuza to determine the complexity of 2-clique-colouring of perfect graphs with all cliques having size at least 3 (Kratochvíl and Tuza (2002) [7]), proving that it is a Σ2P-complete problem. We then determine a hierarchy of nested subclasses of perfect graphs with all cliques having size at least 3 whereby each graph class is in a distinct complexity class, namely Σ2P-complete, NPNP-complete, and PP.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 618, 7 March 2016, Pages 122–134
نویسندگان
, , ,