DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

https://doi.org/10.7151/dmgt

Discussiones Mathematicae Graph Theory

IMPACT FACTOR 2018: 0.741

SCImago Journal Rank (SJR) 2018: 0.763

Rejection Rate (2017-2018): c. 84%

Discussiones Mathematicae Graph Theory

PDF

Discussiones Mathematicae Graph Theory 21(1) (2001) 77-93
DOI: 10.7151/dmgt.1134

ON GRAPHS ALL OF WHOSE {C3,T3}-FREE ARC COLORATIONS ARE KERNEL-PERFECT

Hortensia Galeana-Sánchez and José de Jesús García-Ruvalcaba

Instituto de Matemáticas, UNAM
Universidad Nacional Autónoma de México
Ciudad Universitaria
04510, México, D.F., Mexico

Abstract

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 T3 and C3, 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 C3 or T3, 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 K3 or a star.

Keywords: kernel, kernel-perfect digraph, m-coloured digraph.

2000 Mathematics Subject Classification: 05C20.

References

[1] H. Galeana-Sánchez and J.J. García, Kernels in the closure of coloured digraphs, submitted.
[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.

Received 27 September 2000
Revised 15 February 2001