A note on totally-omnitonal graphs

Abstract: Let the edges of the complete graph

K_{n}

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

K_{n}

contains a copy of

G

with

r

red edges and

b

blue edges for any

r, b g e q 0

with

r + b = e (G)

. If ot(n,G) exists for every sufficiently large

n

, we say that

G

is emph{omnitonal}. Omnitonal graphs were introduced by Caro, Hansberg and Montejano [arXiv:1810.12375,2019]. Now let

G_{1}

,

G_{2}

be two copies of

G

with their edges coloured red or blue. If there is a colour-preserving isomorphism from

G_{1}

to

G_{2}

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

K_{n}

contains all non-quivalent colourings of

G

with

r

red edges and

b

blue edges for any

r, b g e q 0

with

r + b = e (G)

. If tot(n, G) exists for every sufficiently large

n

, we say that G is emph{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.

Recommendations

Cited in

(7)

This page was built for publication: A note on totally-omnitonal graphs

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