Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: m-coloured digraph

Sortuj według:

Ogranicz wyniki do:

Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik

On graphs all of whose {C₃,T₃}-free arc colorations are kernel-perfect

100%

Galeana-Sánchez H., García-Ruvalcaba J.

Discussiones Mathematicae Graph Theory

2001

tom 21

nr 1

77-93

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.

Monochromatic paths and monochromatic sets of arcs in 3-quasitransitive digraphs

88%

Galeana-Sánchez H., Rojas-Monroy R., Zavala B.

Discussiones Mathematicae Graph Theory

2009

tom 29

nr 2

337-347

We call the digraph D an m-coloured digraph if the arcs of D are coloured with m colours. A directed path is called monochromatic if all of its arcs are coloured alike. A set N of vertices of D is called a kernel by monochromatic paths if for every pair of vertices of N there is no monochromatic path between them and for every vertex v ∉ N there is a monochromatic path from v to N. We denote by A⁺(u) the set of arcs of D that have u as the initial vertex. We prove that if D is an m-coloured 3-quasitransitive digraph such that for every vertex u of D, A⁺(u) is monochromatic and D satisfies some colouring conditions over one subdigraph of D of order 3 and two subdigraphs of D of order 4, then D has a kernel by monochromatic paths.

Ograniczanie wyników

2 Discussiones Mathematicae Graph Theory

2 Galeana-Sánchez H.

1 García-Ruvalcaba J.

1 Rojas-Monroy R.

1 Zavala B.

1 2009

1 2001

Wyniki wyszukiwania

On graphs all of whose {C₃,T₃}-free arc colorations are kernel-perfect

Monochromatic paths and monochromatic sets of arcs in 3-quasitransitive digraphs