- Tytuł:
- On graphs all of whose {C₃,T₃}-free arc colorations are kernel-perfect
- Autorzy:
-
Galeana-Sánchez, Hortensia
García-Ruvalcaba, José - Powiązania:
- https://bibliotekanauki.pl/articles/743429.pdf
- Data publikacji:
- 2001
- Wydawca:
- Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
- Tematy:
-
kernel
kernel-perfect digraph
m-coloured digraph - Opis:
-
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. - Źródło:
-
Discussiones Mathematicae Graph Theory; 2001, 21, 1; 77-93
2083-5892 - Pojawia się w:
- Discussiones Mathematicae Graph Theory
- Dostawca treści:
- Biblioteka Nauki
Artykuł