1. Rainbow Triangles in Arc-Colored Tournaments
- Author
-
Ruonan Li, Yandong Bai, Wei Li, and Shenggui Zhang
- Subjects
Vertex (graph theory) ,Mathematics::Combinatorics ,Degree (graph theory) ,0211 other engineering and technologies ,Order (ring theory) ,021107 urban & regional planning ,Rainbow ,0102 computer and information sciences ,02 engineering and technology ,01 natural sciences ,Theoretical Computer Science ,Combinatorics ,Computer Science::Discrete Mathematics ,010201 computation theory & mathematics ,Maximum difference ,Discrete Mathematics and Combinatorics ,Mathematics - Abstract
Let $$T_{n}$$ be an arc-colored tournament of order n. The maximum monochromatic indegree $$\varDelta ^{-mon}(T_{n})$$ (resp. outdegree $$\varDelta ^{+mon}(T_{n})$$ ) of $$T_{n}$$ is the maximum number of in-arcs (resp. out-arcs) of a same color incident to a vertex of $$T_{n}$$ . The irregularity $$i(T_{n})$$ of $$T_{n}$$ is the maximum difference between the indegree and outdegree of a vertex of $$T_{n}$$ . A subdigraph H of an arc-colored digraph D is called rainbow if each pair of arcs in H have distinct colors. In this paper, we show that each vertex v in an arc-colored tournament $$T_{n}$$ with $$\varDelta ^{-mon}(T_n)\le \varDelta ^{+mon}(T_n)$$ is contained in at least $$\frac{\delta (v)(n-\delta (v)-i(T_n))}{2}-[\varDelta ^{-mon}(T_{n})(n-1)+\varDelta ^{+mon}(T_{n})d^+(v)]$$ rainbow triangles, where $$\delta (v)=\min \{d^+(v), d^-(v)\}$$ . We also give some maximum monochromatic degree conditions for $$T_{n}$$ to contain rainbow triangles, and to contain rainbow triangles passing through a given vertex. Finally, we present some examples showing that some of the conditions in our results are best possible.
- Published
- 2021
- Full Text
- View/download PDF