IMI Interdisciplinary Mathematics InstituteCollege of Arts and Sciences

Anti-Ramsey number of edge-disjoint rainbow spanning trees in all graphs

  • Sept. 3, 2021
  • 2:30 p.m.

Abstract

An edge-colored graph $H$ is called \textit{rainbow} if every edge of $H$ receives a different color. Given any host multigraph $G$, the \textit{anti-Ramsey} number of $t$ edge-disjoint rainbow spanning trees in $G$, denoted by $r(G,t)$, is defined as the maximum number of colors in an edge-coloring of $G$ containing no $t$ edge-disjoint rainbow spanning trees. For any vertex partition $P$, let $E(P,G)$ be the set of non-crossing edges in $G$ with respect to $P$. In this talk, we determine $r(G,t)$ for all host multigraphs $G$: $r(G,t)=|E(G)|$ if there exists a partition $P _ 0$ with $|E(G)|-|E(P _ 0,G)|<t(|P _ 0|-1)$; and $r(G,t)=\max _ {P\colon |P|\geq 3} \{|E(P,G)|+t(|P|-2)\}$ otherwise. As a corollary, we determine $r(K _ {p,q},t)$ for all values of $p,q, t$, improving a result of Jia, Lu and Zhang.

This is joint work with Zhiyu Wang and Linyuan Lu.

© Interdisciplinary Mathematics Institute | The University of South Carolina Board of Trustees | Webmaster
USC