On panchromatic patterns

详细信息    查看全文

• 作者：Hortensia Galeana-Sá ; nchez ^{hgaleana@math.unam.mx" class="auth_mail" title="E-mail the corresponding author} ; Ricardo Strausz ; ^{dino@math.unam.mx" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Kernels in digraphs ; Panchromatic ; Patterns
• 刊名：Discrete Mathematics
• 出版年：2016
• 出版时间：6 October 2016
• 年：2016
• 卷：339
• 期：10
• 页码：2536-2542
• 全文大小：717 K

文摘

Since the classic book of Berge (1985) it is well known that every digraph contains a kernel by paths. This was generalised by Sands et al. (1982) who proved that every edge two-coloured digraph has a kernel by monochromatic paths. More generally, given ccfc2f176ad6ed20c4ee65e2e670d9" title="Click to view the MathML source">D$D$ and H$H$ two digraphs, ccfc2f176ad6ed20c4ee65e2e670d9" title="Click to view the MathML source">D$D$ is H$H$-coloured iff the arcs of ccfc2f176ad6ed20c4ee65e2e670d9" title="Click to view the MathML source">D$D$ are coloured with the vertices of H$H$. Furthermore, an H$H$-walk in ccfc2f176ad6ed20c4ee65e2e670d9" title="Click to view the MathML source">D$D$ is a sequence of arcs forming a walk in ccfc2f176ad6ed20c4ee65e2e670d9" title="Click to view the MathML source">D$D$ whose colours are a walk in H$H$. With this notion of H$H$-walks, we can define H$H$-independence, which is the absence of such a walk pairwise, and H$H$-absorbance, which is the existence of such a walk towards the absorbent set. Thus, an H$H$-kernel is a subset of vertices which is both H$H$-independent and H$H$-absorbent. The aim of this paper is to characterise those H$H$, which we call panchromatic patterns  , for which all ccfc2f176ad6ed20c4ee65e2e670d9" title="Click to view the MathML source">D$D$ and all H$H$-colourings of ccfc2f176ad6ed20c4ee65e2e670d9" title="Click to view the MathML source">D$D$ admits an H$H$-kernel. This solves a problem of Arpin and Linek from 2007 (Arpin and Linek, 2007).