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

DOI10.1016/J.ENDM.2009.11.010zbMath1268.05083OpenAlexW2023441208MaRDI QIDQ2840514

Arnaud Pêcher, Annegret K. Wagler

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

polytopecircular-perfect graphpolynomial time computabilitycircular-chromatic numbercircular-clique number

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Perfect graphs (05C17)

Related Items (2)

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

Cites Work

• Unnamed Item
• Unnamed Item
• 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

This page was built for publication: On the polynomial time computability of the circular-chromatic number for some superclasses of perfect graphs