Kernels in edge-colored digraphs

✍ Scribed by Hortensia Galeana-Sánchez

• Book ID: 104113955
• Publisher: Elsevier Science
• Year: 1998
• Tongue: English
• Weight: 647 KB
• Volume: 184
• Category: Article
• ISSN: 0012-365X
• DOI: 10.1016/s0012-365x(97)00162-3

✦ Synopsis

We call the digraph D an m-coloured digraph if the arcs of D are coloured with m colours. A directed path is called monochromatic if all of its arcs are coloured alike. A directed cycle is called quasi-monochromatic if with at most one exception all of its arcs are coloured alike. A set N C__ V(D) is said to be a kernel by monochromatic paths if it satisfies the following two conditions: (i) for every pair of different vertices u, v C N there is no monochromatic directed path between them and; (ii) for every vertex x E V(D)-N there is a vertex y C N such that there is an xy-monochromatic directed path.

In this paper I survey sufficient conditions for a m-coloured digraph to have a kernel by monochromatic paths. I also prove that if D is an m-coloured digraph resulting from the deletion of a single arc of some m-coloured tournament and every directed cycle of length at most 4 is quasi-monochromatic then D has a kernel by monochromatic paths. (~