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

DOI10.1007/S10107-012-0512-4MaRDI QIDQ378133zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

chromatic numberclique numbercircular-perfect graph

Mathematics Subject Classification ID

Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Combinatorial optimization (90C27)

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

Cites work

• scientific article; zbMATH DE number 3882470 (Why is no real title available?)
• scientific article; zbMATH DE number 3563170 (Why is no real title available?)
• scientific article; zbMATH DE number 1455118 (Why is no real title available?)
• scientific article; zbMATH DE number 969115 (Why is no real title available?)
• A characterization of perfect graphs
• A note on the star chromatic number
• Circular perfect graphs
• Claw-free circular-perfect graphs
• Clique and chromatic number of circular-perfect graphs
• Convex-round graphs are circular-perfect
• On certain polytopes associated with graphs
• On classes of minimal circular-imperfect graphs
• On rank-perfect subclasses of near-bipartite graphs
• On the Shannon capacity of a graph
• On the polynomial time computability of the circular-chromatic number for some superclasses of perfect graphs
• Perfect zero–one matrices
• Some simplified NP-complete graph problems
• Star chromatic number
• The NP-Completeness of Edge-Coloring
• The complexity of determining a shortest cycle of even length
• The ellipsoid method and its consequences in combinatorial optimization
• The four-colour theorem
• Triangle-free strongly 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
• scientific article; zbMATH DE number 6096704 (Why is no real title available?)

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)