Polynomial time computability of some graph parameters for superclasses of perfect graphs
\textit{X. Zhu} [J. Graph Theory 48, No. 3, 186--209 (2005; Zbl 1071.05037)] defined the circular chromatic number and the circular clique number of a graph and introduced circular-perfect graphs similar to perfect graphs. So far we do not have polynomial time algorithms computing these parameters, even if the inputs are restricted to circular perfect graphs. The authors restrict the inputs further to graphs \(G=(V,E)\) where \(G[N(v)]\) is perfect for every vertex \(v \in V\), and use polyhedral arguments to obtain polynomial time algorithms computing weighted versions of the circular chromatic number and the circular clique number.
- On the polynomial time computability of the circular-chromatic number for some superclasses of perfect graphs
- Computing clique and chromatic number of circular-perfect graphs in polynomial time
- Clique and chromatic number of circular-perfect graphs
- Computing the clique number of \(a\)-perfect graphs in polynomial time
- Computing the clique number of a-perfect graphs in polynomial time
- On circular-perfect graphs: a survey
- On the theta number of powers of cycle graphs
- Computing the clique number of \(a\)-perfect graphs in polynomial time
- On the polynomial time computability of the circular-chromatic number for some superclasses of perfect graphs
- Computing the clique number of a-perfect graphs in polynomial time
- Clique and chromatic number of circular-perfect graphs
- Computing clique and chromatic number of circular-perfect graphs in polynomial time
- Beyond perfection: computational results for superclasses
This page was built for publication: Polynomial time computability of some graph parameters for superclasses of perfect graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1758876)
