Kernels in the closure of coloured digraphs

• Volume: 20, Issue: 2, page 243-254
• ISSN: 2083-5892

top

Abstract

top
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\left(\xi \left(D\right)\right)={\bigcup }_{i}\left(u,v\right)withcolourithereexistsamonochromaticpathofcolourifromthevertexutothevertexvcontainedinD.$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.

How to cite

top

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 -

References

top
1. [1] C. Berge and P. Duchet, Recent problems and results about kernels in directed graphs, Discrete Math. 86 (1990) 27-31, doi: 10.1016/0012-365X(90)90346-J. Zbl0721.05027
2. [2] H. Galeana-Sánchez, On monochromatic paths and monochromatic cycles in edge coloured tournaments, Discrete Math. 156 (1996) 103-112, doi: 10.1016/0012-365X(95)00036-V. Zbl0857.05054
3. [3] H. Galeana-Sánchez, Kernels in edge coloured digraphs, Discrete Math. 184 (1998) 87-99, doi: 10.1016/S0012-365X(97)00162-3. Zbl0958.05061
4. [4] H. Galeana-Sánchez and J.J. García-Ruvalcaba, On graph all of whose {C₃, T₃}-free arc colorations are kernel-perfect, submitted. Zbl0990.05060
5. [5] 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
6. [6] B. Sands, N. Sauer and R. Woodrow, On monochromatic paths in edge-coloured digraphs, J. Combin. Theory (B) 33 (1982) 271-275, doi: 10.1016/0095-8956(82)90047-8. Zbl0488.05036

top

NotesEmbed?

top

You must be logged in to post comments.

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.