# Nesetril, Jaroslav

## Strong edge colouring conjecture ★★

Author(s): Erdos; Nesetril

A strong edge-colouring of a graph is a edge-colouring in which every colour class is an induced matching; that is, any two vertices belonging to distinct edges with the same colour are not adjacent. The strong chromatic index is the minimum number of colours in a strong edge-colouring of .

Conjecture

Keywords:

## Long rainbow arithmetic progressions ★★

Author(s): Fox; Jungic; Mahdian; Nesetril; Radoicic

For let denote the minimal number such that there is a rainbow in every equinumerous -coloring of for every

Conjecture   For all , .

Keywords: arithmetic progression; rainbow

## Pentagon problem ★★★

Author(s): Nesetril

Question   Let be a 3-regular graph that contains no cycle of length shorter than . Is it true that for large enough~ there is a homomorphism ?

Keywords: cubic; homomorphism