On the polynomial time computability of the circular-chromatic number for some superclasses of perfect graphs

DOI10.1016/j.endm.2009.11.010zbMath1268.05083MaRDI QIDQ2840514

Annegret K. Wagler, Arnaud Pêcher

Publication date: 19 July 2013

Published in: Electronic Notes in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.endm.2009.11.010

zbMATH Keywords

polytope; circular-perfect graph; polynomial time computability; circular-chromatic number; circular-clique number

Mathematics Subject Classification ID

05C15: Coloring of graphs and hypergraphs

05C17: Perfect graphs

Related Items

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

Cites Work

• The strong perfect graph theorem
• Triangle-free strongly circular-perfect graphs
• The ellipsoid method and its consequences in combinatorial optimization
• On certain polytopes associated with graphs
• Minimal circular-imperfect graphs of large clique number and large independence number
• On rank-perfect subclasses of near-bipartite graphs
• Some results on circular perfect graphs and perfect graphs
• Three classes of minimal circular-imperfect graphs
• A note on the star chromatic number
• Star chromatic number
• Circular perfect graphs
• On the circular chromatic number of circular partitionable graphs
• Unnamed Item
• Unnamed Item