On vertex orderings and the stability number in triangle-free graphs

DOI10.1016/S0012-365X(00)00335-6zbMath0983.05071MaRDI QIDQ5937606

Dieter Rautenbach

Publication date: 21 April 2002

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

zbMATH Keywords

greedy algorithm; characterization; stability number; forbidden induced subgraphs; maximal stable set; triangle-free graphs

Mathematics Subject Classification ID

05C75: Structural characterization of families of graphs

05C85: Graph algorithms (graph-theoretic aspects)

Related Items

GreedyMAX-type Algorithms for the Maximum Independent Set Problem