Skip to Main content Skip to Navigation
Book sections

Even Pairs

Hazel Everett 1 Celina M. H. de Figueiredo Claudia Linhares Sales Frederic Maffray Oscar Porto Bruce Reed 
1 ISA - Models, algorithms and geometry for computer graphics and vision
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
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.
Document type :
Book sections
Complete list of metadata
Contributor : Publications Loria Connect in order to contact the contributor
Submitted on : Tuesday, September 26, 2006 - 2:47:27 PM
Last modification on : Friday, February 4, 2022 - 3:32:58 AM


  • HAL Id : inria-00100553, version 1



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⟩



Record views