Kernels in the closure of coloured digraphs

Hortensia Galeana-Sánchez, and José de Jesús García-Ruvalcaba. "Kernels in the closure of coloured digraphs." Discussiones Mathematicae Graph Theory 20.2 (2000): 243-254. <http://eudml.org/doc/270579>.

@article{HortensiaGaleana2000,
abstract = {Let D be a digraph with V(D) and A(D) the sets of vertices and arcs of D, respectively. A kernel of D is a set I ⊂ V(D) such that no arc of D joins two vertices of I and for each x ∈ V(D)∖I there is a vertex y ∈ I such that (x,y) ∈ A(D). A digraph is kernel-perfect if every non-empty induced subdigraph of D has a kernel. If D is edge coloured, we define the closure ξ(D) of D the multidigraph with 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\}. $Let T₃ and C₃ denote the transitive tournament of order 3 and the 3-cycle, respectively, both of whose arcs are coloured with 3 different colours. In this paper, we survey sufficient conditions for the existence of kernels in the closure of edge coloured digraphs, also we prove that if D is obtained from an edge coloured tournament by deleting one arc and D does not contain T₃ or C₃, then ξ(D) is a kernel-perfect digraph.},
author = {Hortensia Galeana-Sánchez, José de Jesús García-Ruvalcaba},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {kernel; closure; tournament; -coloured digraph},
language = {eng},
number = {2},
pages = {243-254},
title = {Kernels in the closure of coloured digraphs},
url = {http://eudml.org/doc/270579},
volume = {20},
year = {2000},
}

TY - JOUR
AU - Hortensia Galeana-Sánchez
AU - José de Jesús García-Ruvalcaba
TI - Kernels in the closure of coloured digraphs
JO - Discussiones Mathematicae Graph Theory
PY - 2000
VL - 20
IS - 2
SP - 243
EP - 254
AB - Let D be a digraph with V(D) and A(D) the sets of vertices and arcs of D, respectively. A kernel of D is a set I ⊂ V(D) such that no arc of D joins two vertices of I and for each x ∈ V(D)∖I there is a vertex y ∈ I such that (x,y) ∈ A(D). A digraph is kernel-perfect if every non-empty induced subdigraph of D has a kernel. If D is edge coloured, we define the closure ξ(D) of D the multidigraph with 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}. $Let T₃ and C₃ denote the transitive tournament of order 3 and the 3-cycle, respectively, both of whose arcs are coloured with 3 different colours. In this paper, we survey sufficient conditions for the existence of kernels in the closure of edge coloured digraphs, also we prove that if D is obtained from an edge coloured tournament by deleting one arc and D does not contain T₃ or C₃, then ξ(D) is a kernel-perfect digraph.
LA - eng
KW - kernel; closure; tournament; -coloured digraph
UR - http://eudml.org/doc/270579
ER -