On kernels by rainbow paths in arc-coloured digraphs

DOI10.1515/MATH-2021-0019zbMATH Open1475.05074arXiv1807.08286OpenAlexW3165750979MaRDI QIDQ2053604FDOQ2053604

Yanqin Cao, Ruijuan Li, Xinhong Zhang

Publication date: 29 November 2021

Published in: Open Mathematics (Search for Journal in Brave)

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.

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• On monochromatic paths in edge-coloured digraphs
• Digraphs
• On monochromatic paths in m-coloured tournaments
• Kernels in edge-colored digraphs
• Kernels by properly colored paths in arc-colored digraphs
• A counterexample to a conjecture on edge-coloured tournaments
• On monochromatic paths and monochromatic cycles in edge coloured tournaments
• Graphes Noyau-Parfaits
• On monochromatic paths and monochromatic 4-cycles in edge coloured bipartite tournaments
• Independent domination by monochromatic paths in arc coloured bipartite tournaments
• \(H\)-kernels by walks in \(H\)-colored digraphs and the color-class digraph
• Alternating kernels
• 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)