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
perfect graphsweakly chordal graphs(alpha, beta)-polar graphsclique-colouringhierarchical complexity\((\alpha, \beta)\)-polar graphs
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
This page was built for publication: Hierarchical complexity of 2-clique-colouring weakly chordal graphs and perfect graphs having cliques of size at least 3
