On kernels by rainbow paths in arc-coloured digraphs

DOI10.1515/MATH-2021-0019MaRDI QIDQ2053604zbMATH OpenOpenAlexFDO

Authors Ruijuan Li, Yanqin Cao, Xinhong Zhang

Publication date 29 November 2021

Published in Open Mathematics (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/1807.08286

zbMATH Keywords

kernelsarc-coloured digraphskernels by rainbow paths

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Vertex degrees (05C07) Distance in graphs (05C12)

Abstract: In 2018, Bai, Fujita and Zhang (emph{Discrete Math.} 2018, 341(6): 1523-1533) introduced the concept of a kernel by rainbow paths (for short, RP-kernel) of an arc-coloured digraph $D$, which is a subset $S$ of vertices of $D$ such that ($a$) there exists no rainbow path for any pair of distinct vertices of $S$, and ($b$) every vertex outside $S$ can reach $S$ by a rainbow path in $D$. They showed that it is NP-hard to recognize wether an arc-coloured digraph has a RP-kernel and it is NP-complete to decided wether an arc-coloured tournament has a RP-kernel. In this paper, we give the sufficient conditions for the existence of a RP-kernel in arc-coloured unicyclic digraphs, semicomplete digraphs, quasi-transitive digraphs and bipartite tournaments, and prove that these arc-coloured digraphs have RP-kernels if certain "short" cycles and certain "small" induced subdigraphs are rainbow.

Recommendations

• Kernels by rainbow paths in arc-colored tournaments
• Kernels by properly colored paths in arc-colored digraphs
• Kernels by monochromatic paths and color-perfect digraphs
• Kernels in edge-colored digraphs
• Alternating kernels

Cites work

• scientific article; zbMATH DE number 3106184 (Why is no real title available?)
• A counterexample to a conjecture on edge-coloured tournaments
• Alternating domination in arc-colored digraphs.
• Alternating kernels
• Digraphs
• Graphes Noyau-Parfaits
• Independent domination by monochromatic paths in arc coloured bipartite tournaments
• Kernels by properly colored paths in arc-colored digraphs
• Kernels by rainbow paths in arc-colored tournaments
• Kernels in edge-colored digraphs
• On monochromatic paths and monochromatic 4-cycles in edge coloured bipartite tournaments
• On monochromatic paths and monochromatic cycles in edge coloured tournaments
• On monochromatic paths in edge-coloured digraphs
• On monochromatic paths in m-coloured tournaments
• \(H\)-kernels by walks in \(H\)-colored digraphs and the color-class digraph

Cited in

(1)

• Kernels by rainbow paths in arc-colored tournaments

This page was built for publication: On kernels by rainbow paths in arc-coloured digraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2053604)