Back to Search Start Over

Rainbow Triangles in Arc-Colored Tournaments

Authors :
Ruonan Li
Yandong Bai
Wei Li
Shenggui Zhang
Source :
Graphs and Combinatorics. 37:1271-1290
Publication Year :
2021
Publisher :
Springer Science and Business Media LLC, 2021.

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.

Details

ISSN :
14355914 and 09110119
Volume :
37
Database :
OpenAIRE
Journal :
Graphs and Combinatorics
Accession number :
edsair.doi...........5182a3ba35b8fc6b425152b7fbde5c02