Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4650622 | Discrete Mathematics | 2006 | 8 Pages |
Abstract
In this paper we give a characterization of kernel-perfect (and of critical kernel-imperfect) arc-local tournament digraphs. As a consequence, we prove that arc-local tournament digraphs satisfy a strenghtened form of the following interesting conjecture which constitutes a bridge between kernels and perfectness in digraphs, stated by C. Berge and P. Duchet in 1982: a graph G is perfect if and only if any normal orientation of G is kernel-perfect. We prove a variation of this conjecture for arc-local tournament orientable graphs. Also it is proved that normal arc-local tournament orientable graphs satisfy a stronger form of Berge's strong perfect graph conjecture.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Hortensia Galeana-Sánchez,