Improved bounds for the triangle case of Aharoni's rainbow generalization of the Caccetta-Häggkvist conjecture

DOI10.1016/J.DISC.2023.113691MaRDI QIDQ6080148zbMATH OpenWikidataFDO

Authors Patrick Hompe, Zishen Qu, Sophie Spirkl

Publication date 30 October 2023

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2206.10733

zbMATH Keywords

Caccetta-Häggkvist conjecturedirected graphrainbow cycle

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Directed graphs (digraphs), tournaments (05C20)

Abstract: For a digraph $G$ and $vinV(G)$, let $delt{a}^{+}(v)$ be the number of out-neighbors of $v$ in $G$. The Caccetta-H"{a}ggkvist conjecture states that for all $kge1$, if $G$ is a digraph with $n=|V(G)|$ such that $delt{a}^{+}(v)gek$ for all $vinV(G)$, then $G$ contains a directed cycle of length at most $lceiln/kceil$. Aharoni proposed a generalization of this conjecture, that a simple edge-colored graph on $n$ vertices with $n$ color classes, each of size at least $k$, has a rainbow cycle of length at most $lceiln/kceil$. Let $$ be emph{triangular} if a simple edge-colored graph on $n$ vertices with at least $alphan$ color classes, each with at least $$ edges, must have a rainbow triangle. Aharoni, Holzman, and DeVos showed the following: $(9/8,1/3)$ is triangular; and $(1,2/5)$ is triangular. In this paper, we improve those bounds, showing the following: $(1.1077,1/3)$ is triangular; and $(1,0.3988)$ is triangular.

Recommendations

• Rainbow triangles and the Caccetta-Häggkvist conjecture
• Further approximations for Aharoni's rainbow generalization of the Caccetta-Häggkvist conjecture
• On Aharoni's rainbow generalization of the Caccetta-Häggkvist conjecture
• Short rainbow cycles for families of matchings and triangles
• Notes on Aharoni's rainbow cycle conjecture

Cites work

• Further approximations for Aharoni's rainbow generalization of the Caccetta-Häggkvist conjecture
• Graphs with maximal number of adjacent pairs of edges
• scientific article; zbMATH DE number 3630786 (Why is no real title available?)
• On Sets of Acquaintances and Strangers at any Party
• Rainbow cycles for families of matchings
• Rainbow triangles and the Caccetta-Häggkvist conjecture

Cited in

(2)

• Minimum-degree conditions for rainbow triangles
• Short rainbow cycles for families of matchings and triangles

This page was built for publication: Improved bounds for the triangle case of Aharoni's rainbow generalization of the Caccetta-Häggkvist conjecture

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