# Kernels by Monochromatic Paths and Color-Perfect Digraphs

Hortensia Galeana-Śanchez; Rocío Sánchez-López

Discussiones Mathematicae Graph Theory (2016)

- Volume: 36, Issue: 2, page 309-321
- ISSN: 2083-5892

## Access Full Article

top## Abstract

top## How to cite

topHortensia Galeana-Śanchez, and Rocío Sánchez-López. "Kernels by Monochromatic Paths and Color-Perfect Digraphs." Discussiones Mathematicae Graph Theory 36.2 (2016): 309-321. <http://eudml.org/doc/277132>.

@article{HortensiaGaleana2016,

abstract = {For a digraph D, V (D) and A(D) will denote the sets of vertices and arcs of D respectively. In an arc-colored digraph, a subset K of V(D) is said to be kernel by monochromatic paths (mp-kernel) if (1) for any two different vertices x, y in N there is no monochromatic directed path between them (N is mp-independent) and (2) for each vertex u in V (D) N there exists v ∈ N such that there is a monochromatic directed path from u to v in D (N is mp-absorbent). If every arc in D has a different color, then a kernel by monochromatic paths is said to be a kernel. Two associated digraphs to an arc-colored digraph are the closure and the color-class digraph CC(D). In this paper we will approach an mp-kernel via the closure of induced subdigraphs of D which have the property of having few colors in their arcs with respect to D. We will introduce the concept of color-perfect digraph and we are going to prove that if D is an arc-colored digraph such that D is a quasi color-perfect digraph and CC(D) is not strong, then D has an mp-kernel. Previous interesting results are generalized, as for example Richardson′s Theorem.},

author = {Hortensia Galeana-Śanchez, Rocío Sánchez-López},

journal = {Discussiones Mathematicae Graph Theory},

keywords = {kernel; kernel perfect digraph; kernel by monochromatic paths; color-class digraph; quasi color-perfect digraph; color-perfect digraph},

language = {eng},

number = {2},

pages = {309-321},

title = {Kernels by Monochromatic Paths and Color-Perfect Digraphs},

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

volume = {36},

year = {2016},

}

TY - JOUR

AU - Hortensia Galeana-Śanchez

AU - Rocío Sánchez-López

TI - Kernels by Monochromatic Paths and Color-Perfect Digraphs

JO - Discussiones Mathematicae Graph Theory

PY - 2016

VL - 36

IS - 2

SP - 309

EP - 321

AB - For a digraph D, V (D) and A(D) will denote the sets of vertices and arcs of D respectively. In an arc-colored digraph, a subset K of V(D) is said to be kernel by monochromatic paths (mp-kernel) if (1) for any two different vertices x, y in N there is no monochromatic directed path between them (N is mp-independent) and (2) for each vertex u in V (D) N there exists v ∈ N such that there is a monochromatic directed path from u to v in D (N is mp-absorbent). If every arc in D has a different color, then a kernel by monochromatic paths is said to be a kernel. Two associated digraphs to an arc-colored digraph are the closure and the color-class digraph CC(D). In this paper we will approach an mp-kernel via the closure of induced subdigraphs of D which have the property of having few colors in their arcs with respect to D. We will introduce the concept of color-perfect digraph and we are going to prove that if D is an arc-colored digraph such that D is a quasi color-perfect digraph and CC(D) is not strong, then D has an mp-kernel. Previous interesting results are generalized, as for example Richardson′s Theorem.

LA - eng

KW - kernel; kernel perfect digraph; kernel by monochromatic paths; color-class digraph; quasi color-perfect digraph; color-perfect digraph

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

ER -

## NotesEmbed ?

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