Balanced independent sets in graphs omitting large cliques

Abstract: Our goal is to investigate a close relative of the independent transversal problem in the class of infinite

K_{n}

-free graphs: we show that for any infinite

K_{n}

-free graph

G = (V, E)

and

m i n m a t h b b N

there is a minimal

r = r (G, m)

such that for any balanced

r

-colouring of the vertices of

G

one can find an independent set which meets at least

m

colour classes in a set of size

| V |

. Answering a conjecture of S. Thomass'e, we express the exact value of

r (H_{n}, m)

(using Ramsey-numbers for finite digraphs), where

H_{n}

is Henson's countable universal homogeneous

K_{n}

-free graph. In turn, we deduce a new partition property of

H_{n}

regarding balanced embeddings of bipartite graphs: for any finite bipartite

G

with bipartition

A, B

, if the vertices of

H_{n}

are partitioned into two infinite classes then there is an induced copy of

G

in

H_{n}

such that the images of

A

and

B

are contained in different classes.

Cites Work

Cited In (1)

This page was built for publication: Balanced independent sets in graphs omitting large cliques