A digraph D is called a kernel-perfect digraph or KP-digraph when every induced subdigraph of D has a kernel. We call the digraph D an m-coloured digraph if the arcs of D are coloured with m distinct colours. A path P is monochromatic in D if all of its arcs are coloured alike in D. The closure of D, denoted by ζ(D), is the m-coloured digraph defined as follows: V( ζ(D)) = V(D), and A( ζ(D)) = ∪_{i} {(u,v) with colour i: there exists a monochromatic path of colour i from the vertex u to the vertex v contained in D}. We will denoted by T₃ and C₃, the transitive tournament of order 3 and the 3-directed-cycle respectively; both of whose arcs are coloured with three different colours. Let G be a simple graph. By an m-orientation-coloration of G we mean an m-coloured digraph which is an asymmetric orientation of G. By the class E we mean the set of all the simple graphs G that for any m-orientation-coloration D without C₃ or T₃, we have that ζ(D) is a KP-digraph. In this paper we prove that if G is a hamiltonian graph of class E, then its complement has at most one nontrivial component, and this component is K₃ or a star.
@article{bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1134,
author = {Hortensia Galeana-S\'anchez and Jos\'e de Jes\'us Garc\'\i a-Ruvalcaba},
title = {On graphs all of whose {C3,T3}-free arc colorations are kernel-perfect},
journal = {Discussiones Mathematicae Graph Theory},
volume = {21},
year = {2001},
pages = {77-93},
zbl = {0990.05060},
language = {en},
url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1134}
}
Hortensia Galeana-Sánchez; José de Jesús García-Ruvalcaba. On graphs all of whose {C₃,T₃}-free arc colorations are kernel-perfect. Discussiones Mathematicae Graph Theory, Tome 21 (2001) pp. 77-93. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1134/
[000] [1] H. Galeana-Sánchez and J.J. García, Kernels in the closure of coloured digraphs, submitted. | Zbl 0990.05059
[001] [2] Shen Minggang, On monochromatic paths in m-coloured tournaments, J. Combin. Theory (B) 45 (1988) 108-111, doi: 10.1016/0095-8956(88)90059-7. | Zbl 0654.05033