pith. machine review for the scientific record.
sign in

arxiv: 1810.05960 · v1 · pith:PSEWWX6Fnew · submitted 2018-10-14 · 🧮 math.CO

Rainbow triangles in arc-colored digraphs

classification 🧮 math.CO
keywords overleftrightarrowrainbowarc-coloreddigraphnumbertrianglearcscolors
0
0 comments X
read the original abstract

Let $D$ be an arc-colored digraph. The arc number $a(D)$ of $D$ is defined as the number of arcs of $D$. The color number $c(D)$ of $D$ is defined as the number of colors assigned to the arcs of $D$. A rainbow triangle in $D$ is a directed triangle in which every pair of arcs have distinct colors. Let $f(D)$ be the smallest integer such that if $c(D)\geq f(D)$, then $D$ contains a rainbow triangle. In this paper we obtain $f(\overleftrightarrow{K}_{n})$ and $f(T_n)$, where $\overleftrightarrow{K}_{n}$ is a complete digraph of order $n$ and $T_n$ is a strongly connected tournament of order $n$. Moreover we characterize the arc-colored complete digraph $\overleftrightarrow{K}_{n}$ with $c(\overleftrightarrow{K}_{n})=f(\overleftrightarrow{K}_{n})-1$ and containing no rainbow triangles. We also prove that an arc-colored digraph $D$ on $n$ vertices contains a rainbow triangle when $a(D)+c(D)\geq a(\overleftrightarrow{K}_{n})+f(\overleftrightarrow{K}_{n})$, which is a directed extension of the undirected case.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.