Full Characterization of Color Degree Sequences in Complete Graphs Without Tricolored Triangles

Authors

Publication date 27 April 2023

Abstract: For an edge-colored complete graph, we define the color degree of a node as the number of colors appearing on edges incident to it. In this paper, we consider colorings that don't contain tricolored triangles (also called rainbow triangles); these colorings are also called Gallai colorings. We give a complete characterization of all possible color degree sequences

d_{1} l e d_{2} l e d o t s l e d_{n}

that can arise on a Gallai coloring of

K_{n}

: it is necessary and sufficient that [ sum_{i = k}^n frac{1}{2^{d_i - d_{k-1}}} ge 1 ] holds for all

1 l e k l e n

, where

d_{0} = 0

for convenience. As a corollary, this gives another proof of a 2018 result of Fujita, Li, and Zhang who showed that the minimum color degree in such a coloring is at most

l o g_{2} n

.

This page was built for publication: Full Characterization of Color Degree Sequences in Complete Graphs Without Tricolored Triangles

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6434617)