Any edge colouring For every partition of $K_$E(K_{n,n})$ hasinto $n$ colour classes of size $n$, there is a vertex withincident to at least $\sqrt{n}$ incident edges of different colours

Given a fixed edge colouringpartition of the edges of $K_{n,n}$ that usesinto $n$ colours, where each colour appears exactly n$n$ times, prove that there exists a vertex incident to at least $\sqrt{n}$ colours.

added 40 characters in body

Source Link

edited Feb 3, 2023 at 15:46

Marina Drygala

75
3

Given a fixed edge colouring of $K_{n,n}$ that uses each colour exactly n times, prove that there exists a vertex incident to at least $\sqrt{n}$ colours.

Source Link

asked Feb 3, 2023 at 13:40

Marina Drygala

75
3

Any edge colouring of $K_{n,n}$ has a vertex with at least $\sqrt{n}$ incident edges of different colours

Given a fixed edge colouring of $K_{n,n}$, prove that there exists a vertex incident to at least $\sqrt{n}$ colours.

graph-colorings probabilistic-method

Stack Exchange Network

Return to Question

Any edge colouring For every partition of $K_$E(K_{n,n})$ hasinto $n$ colour classes of size $n$, there is a vertex withincident to at least $\sqrt{n}$ incident edges of different colours

Any edge colouring of $K_{n,n}$ has a vertex with at least $\sqrt{n}$ incident edges of different colours

For every partition of $E(K_{n,n})$ into $n$ colour classes of size $n$, there is a vertex incident to at least $\sqrt{n}$ colours

Any edge colouring of $K_{n,n}$ has a vertex with at least $\sqrt{n}$ incident edges of different colours