Nesetril, Jaroslav


Strong edge colouring conjecture ★★

Author(s): Erdos; Nesetril

A strong edge-colouring of a graph $G$ 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 $s\chi'(G)$ is the minimum number of colours in a strong edge-colouring of $G$.

\begin{conjecture} $$s\chi'(G) \leq \frac{5\Delta^2}{4}, \text{if $\Delta$ is even,}$$ $$s\chi'(G) \leq \frac{5\Delta^2-2\Delta +1}{4},&\text{if $\Delta$ is odd.}$$ \end{conjecture}

Keywords:

Long rainbow arithmetic progressions ★★

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

For $k\in \mathbb{N}$ let $T_k$ denote the minimal number $t\in \mathbb{N}$ such that there is a rainbow $AP(k)$ in every equinumerous $t$-coloring of $\{ 1,2,\ldots ,tn\}$ for every $n\in \mathbb{N}$

\begin{conjecture} For all $k\geq 3$, $T_k=\Theta (k^2)$. \end{conjecture}

Keywords: arithmetic progression; rainbow

Pentagon problem ★★★

Author(s): Nesetril

\begin{question} Let $G$ be a 3-regular graph that contains no cycle of length shorter than $g$. Is it true that for large enough~$g$ there is a \Def[homomorphism]{graph_homomorphism} $G \to C_5$? \end{question}

Keywords: cubic; homomorphism

Syndicate content