Article ID Journal Published Year Pages File Type
4650622 Discrete Mathematics 2006 8 Pages PDF
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
,