Computing clique and chromatic number of circular-perfect graphs in polynomial time
From MaRDI portal
Publication:378133
DOI10.1007/s10107-012-0512-4zbMath1280.90102OpenAlexW2003374739MaRDI QIDQ378133
Annegret K. Wagler, Arnaud Pêcher
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
Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Combinatorial optimization (90C27)
Related Items (3)
Integer round-up property for the chromatic number of some \(h\)-perfect graphs ⋮ On circular-perfect graphs: a survey ⋮ Computing the clique number of \(a\)-perfect graphs in polynomial time
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Triangle-free strongly circular-perfect graphs
- The complexity of determining a shortest cycle of even length
- The ellipsoid method and its consequences in combinatorial optimization
- Some simplified NP-complete graph problems
- The four-colour theorem
- On certain polytopes associated with graphs
- On classes of minimal circular-imperfect graphs
- On rank-perfect subclasses of near-bipartite graphs
- A characterization 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
- Convex-round graphs are circular-perfect
- A note on the star chromatic number
- Star chromatic number
- The NP-Completeness of Edge-Coloring
- On the Shannon capacity of a graph
- Circular perfect graphs
- Perfect zero–one matrices
- Claw‐free circular‐perfect graphs
This page was built for publication: Computing clique and chromatic number of circular-perfect graphs in polynomial time
