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

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

Discussiones Mathematicae Graph Theory (2001)

- Volume: 21, Issue: 1, page 77-93
- ISSN: 2083-5892

## Access Full Article

top## Abstract

top## How to cite

topHortensia Galeana-Sánchez, and José de Jesús García-Ruvalcaba. "On graphs all of whose {C₃,T₃}-free arc colorations are kernel-perfect." Discussiones Mathematicae Graph Theory 21.1 (2001): 77-93. <http://eudml.org/doc/270329>.

@article{HortensiaGaleana2001,

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 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.
},

author = {Hortensia Galeana-Sánchez, José de Jesús García-Ruvalcaba},

journal = {Discussiones Mathematicae Graph Theory},

keywords = {kernel; kernel-perfect digraph; m-coloured digraph; -coloured digraph},

language = {eng},

number = {1},

pages = {77-93},

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

url = {http://eudml.org/doc/270329},

volume = {21},

year = {2001},

}

TY - JOUR

AU - Hortensia Galeana-Sánchez

AU - José de Jesús García-Ruvalcaba

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

JO - Discussiones Mathematicae Graph Theory

PY - 2001

VL - 21

IS - 1

SP - 77

EP - 93

AB -
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.

LA - eng

KW - kernel; kernel-perfect digraph; m-coloured digraph; -coloured digraph

UR - http://eudml.org/doc/270329

ER -

## References

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

## Citations in EuDML Documents

top## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.