Computing clique and chromatic number of circular-perfect graphs in polynomial time

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

zbMATH Keywords

chromatic numberclique numbercircular-perfect graph

Mathematics Subject Classification ID

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