Even Pairs

Abstract : Two nonadjacent vertices x and y in a graph G form an even pair if every induced path between them has an even number of edges. Even pairs have become an imprtant tool for proving that certain classes of graphs are perfect and for designing optimization algorithms on special classes of perfect graphs. This chapter surveys results of these types.It also discusses numerous related concepts including odd pairs.
Type de document :
Chapitre d'ouvrage
Jorge L. Ramirez Alfonsin et Bruce A. Reed. Perfect Graphs, John Wiley and Sons Ltd., 23 p, 2001, Wiley-Interscience Series in Discrete Mathematics and Optimization
Liste complète des métadonnées

https://hal.inria.fr/inria-00100553
Contributeur : Publications Loria <>
Soumis le : mardi 26 septembre 2006 - 14:47:27
Dernière modification le : jeudi 11 janvier 2018 - 06:19:48

Identifiants

  • HAL Id : inria-00100553, version 1

Collections

Citation

Hazel Everett, Celina M. H. De Figueiredo, Claudia Linhares Sales, Frederic Maffray, Oscar Porto, et al.. Even Pairs. Jorge L. Ramirez Alfonsin et Bruce A. Reed. Perfect Graphs, John Wiley and Sons Ltd., 23 p, 2001, Wiley-Interscience Series in Discrete Mathematics and Optimization. 〈inria-00100553〉

Partager

Métriques

Consultations de la notice

136