Computing clique and chromatic number of circular-perfect graphs in polynomial time
From MaRDI portal
Publication:378133
DOI10.1007/S10107-012-0512-4zbMATH Open1280.90102OpenAlexW2003374739MaRDI QIDQ378133FDOQ378133
Authors: Arnaud Pêcher, Annegret K. Wagler 
Publication date: 11 November 2013
Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s10107-012-0512-4
Recommendations
- Clique and chromatic number of circular-perfect graphs
- On the polynomial time computability of the circular-chromatic number for some superclasses of perfect graphs
- Polynomial time computability of some graph parameters for superclasses of perfect graphs
- On circular-perfect graphs: a survey
- Computing the clique number of \(a\)-perfect graphs in polynomial time
Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Combinatorial optimization (90C27)
Cites Work
- On the Shannon capacity of a graph
- The ellipsoid method and its consequences in combinatorial optimization
- On certain polytopes associated with graphs
- A characterization of perfect graphs
- Title not available (Why is that?)
- The NP-Completeness of Edge-Coloring
- Title not available (Why is that?)
- The complexity of determining a shortest cycle of even length
- Some simplified NP-complete graph problems
- The four-colour theorem
- Title not available (Why is that?)
- Circular perfect graphs
- Perfect zero–one matrices
- Star chromatic number
- Title not available (Why is that?)
- Triangle-free strongly circular-perfect graphs
- On classes of minimal circular-imperfect graphs
- On rank-perfect subclasses of near-bipartite graphs
- On the polynomial time computability of the circular-chromatic number for some superclasses of perfect graphs
- Clique and chromatic number of circular-perfect graphs
- Convex-round graphs are circular-perfect
- A note on the star chromatic number
- Claw-free circular-perfect graphs
Cited In (8)
- Beyond perfection: computational results for superclasses
- Computing the clique number of \(a\)-perfect graphs in polynomial time
- Polynomial time computability of some graph parameters for superclasses of perfect graphs
- On the polynomial time computability of the circular-chromatic number for some superclasses of perfect graphs
- Clique and chromatic number of circular-perfect graphs
- Integer round-up property for the chromatic number of some \(h\)-perfect graphs
- On circular-perfect graphs: a survey
- Title not available (Why is that?)
This page was built for publication: Computing clique and chromatic number of circular-perfect graphs in polynomial time
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q378133)
