Monochromatic Sinks in <Emphasis Type="Italic">k</Emphasis>-Arc Colored Tournaments |
| |
Authors: | Adam Bland |
| |
Institution: | 1.Middle Georgia State University,Macon,USA |
| |
Abstract: | Let T be a tournament on n vertices whose arcs are colored with k colors. A 3-cycle whose arcs are colored with three distinct colors is called a rainbow triangle. A rainbow triangle dominated by any nonempty set of vertices is called a dominated rainbow triangle. We prove that when \(n\ge 5\), if T does not contain a dominated rainbow triangle and all 4- and 5-cycles of T are near-monochromatic, then T has a monochromatic sink. We also prove that when \(n\ge 4\), if T does not contain a dominated rainbow triangle and all 4-cycles are monochromatic, then T has a monochromatic sink. A semi-cycle is a digraph C that either is a cycle or contains an arc xy such that \(C-xy+yx\) is a cycle. We prove that if \(n\ge 4\) and all 4-semi-cycles of T are near-monochromatic, then T has a monochromatic sink. We also show if \(n\ge 5\) and all 5-semi-cycles of T are near-monochromatic, then T has a monochromatic sink. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|