New classes of panchromatic digraphs

A digraph with a -colouring of its arcs is said to have a -kernel if there exists a subset of such that there are no monochromatic -paths for any two vertices , but for every , there exists a vertex such that there is a monochromatic -path in . The panchromatic number, , of is the greatest integer f...

Full description

Saved in:
Bibliographic Details
Published in:AKCE International Journal of Graphs and Combinatorics 2015-11, Vol.12 (2-3), p.261-270
Main Authors: Galeana-Sánchez, Hortensia, Toledo, Micael
Format: Article
Language:English
Subjects:
Arc-colouring
kernel
Panchromatic digraph
Panchromatic number
ς-kernel
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:A digraph with a -colouring of its arcs is said to have a -kernel if there exists a subset of such that there are no monochromatic -paths for any two vertices , but for every , there exists a vertex such that there is a monochromatic -path in . The panchromatic number, , of is the greatest integer for which has a -kernel for every possible -colouring of its arcs. is said to be a panchromatic digraph if, for every and every -colouring , has a -kernel. In this paper we study the panchromaticity of cycles. In particular, we show that even cycles are panchromatic and that when is an odd cycle. We also set sufficient conditions, in terms of its induced subdigraphs, for a digraph to be panchromatic, and we show through counterexamples that these results cannot be improved.
ISSN:0972-8600
2543-3474
DOI:10.1016/j.akcej.2015.11.006