Stability number and chromatic number of tolerance graphs

DOI10.1016/0166-218X(92)90203-MzbMath0759.05090MaRDI QIDQ1186162

Rachel Manber, Giri Narasimhan

Publication date: 28 June 1992

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

zbMATH Keywords

stability numberchromatic numberclique numberperfect graphstolerance graphsclique cover

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

Proper and unit tolerance graphs ⋮ Any complete preference structure without circuit admits an interval representation ⋮ On the intersection of tolerance and cocomparability graphs

Cites Work

• Tolerance graphs
• On chain and antichain families of a partially ordered set
• The ellipsoid method and its consequences in combinatorial optimization
• Unnamed Item
• Unnamed Item
• Unnamed Item