A note on totally-omnitonal graphs

Abstract

Let the edges of the complete graph Kn be coloured red or blue, and let G be a graph with |V (G)| < n. Then ot(n, G) is defined to be the minimum integer, if it exists, such that any such colouring of Kn contains a copy of G with r red edges and b blue edges for any r, b ≥ 0 with r + b = e(G). If ot(n, G) exists for every sufficiently large n, we say that G is omnitonal. Omnitonal graphs were introduced by Caro, Hansberg and Montejano [arXiv:1810.12375,2019]. Now let G1, G2 be two copies of G with their edges coloured red or blue. If there is a colour-preserving isomorphism from G1 to G2 we say that the 2-colourings of G are equivalent. Now we define tot(n, G) to be the minimum integer, if it exists, such that any such colouring of Kn contains all non-quivalent colourings of G with r red edges and b blue edges for any r, b ≥ 0 with r + b = e(G). If tot(n, G) exists for every sufficiently large n, we say that G is totally-omnitotal. In this note we show that the only totally-omnitonal graphs are stars or star forests namely a forest all of whose components are stars.