![](/files/happy5.png)
Nesetril, Jaroslav
Strong edge colouring conjecture ★★
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
![$$s\chi'(G) \leq \frac{5\Delta^2}{4}, \text{if $\Delta$ is even,}$$](/files/tex/a63811dfccf4e3128accc3daca7041ff5097e2a2.png)
![$$s\chi'(G) \leq \frac{5\Delta^2-2\Delta +1}{4},&\text{if $\Delta$ is odd.}$$](/files/tex/987d7e1dcf43bb92750a5d1dffe79abc224035c2.png)
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
,
.
![$ k\geq 3 $](/files/tex/c403b537b372cb5d16b6129dce0f0c416c1f1b31.png)
![$ T_k=\Theta (k^2) $](/files/tex/861c6fb3fc588a2247540bcd7bf32e42032ad265.png)
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
?
![$ G $](/files/tex/b8e7ad0330f925492bf468b5c379baec88cf1b3d.png)
![$ g $](/files/tex/4239ee4145983e1d8ad375f0606cc7140bce36a3.png)
![$ g $](/files/tex/4239ee4145983e1d8ad375f0606cc7140bce36a3.png)
![$ G \to C_5 $](/files/tex/090efbbd450a0134afde46b53f2dbe35011946d1.png)
Keywords: cubic; homomorphism
![Syndicate content Syndicate content](/misc/feed.png)