Hierarchical complexity of 2-clique-colouring weakly chordal graphs and perfect graphs having cliques of size at least 3

DOI10.1016/j.tcs.2016.01.027zbMath1335.68106arXiv1312.2086OpenAlexW1923730277MaRDI QIDQ2634675

Hélio B. Macêdo Filho, Raphael C. S. Machado, Celina M. Herrera de Figueiredo, Celina M. H. Figueiredo

Publication date: 18 February 2016

Published in: Theoretical Computer Science, LATIN 2014: Theoretical Informatics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1312.2086

zbMATH Keywords

perfect graphsweakly chordal graphs(alpha, beta)-polar graphsclique-colouringhierarchical complexity\((\alpha, \beta)\)-polar graphs

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Perfect graphs (05C17)

Cites Work

• Unnamed Item
• Complexity of clique coloring and related problems
• The strong perfect graph theorem
• About recognizing (\(\alpha\) ,\(\beta\) ) classes of polar graphs
• Two-colouring all two-element maximal antichains
• Clique-Colouring and Biclique-Colouring Unichord-Free Graphs
• Complexity of clique-coloring odd-hole-free graphs
• Almost all Berge Graphs are Perfect
• Coloring the Maximal Cliques of Graphs
• On the complexity of bicoloring clique hypergraphs of graphs
• The complexity of satisfiability problems