Conjectura de Erdös-Faber-Lovász

Lendo o texto do Béla Bollobás (veja aqui) e parei para pensar em qual problema seria um "sonho" para mim, isto é, um grande problema que eu amaria resolver. Depois de um tempo de reflexão, cheguei a escolha de uma conjectura em Teoria dos Grafos:

Conjectura de Erdös-Faber-Lovász. Se $k$ grafos completos, cada um tendo exatamente $k$ vértices, têm a propriedade de que cada par de grafos compartilham no máximo um vértice, então a união desses grafos pode ser colorida com $k$ cores.

Esta conjectura é de 1972 e pode ser encontrada num artigo do Erdös onde ele fala quais são os problemas que ele gostaria de ver resolvido (veja aqui o artigo).

O seu enunciado não é difícil de entender e esta conjectura tem tentado muitos combinatoristas. E este foi um dos motivos pela qual me interessei por esta conjectura.

A primeira vez que a vi foi num seminário do grupo de pesquisa da qual faço parte, o ParGO (link). Lá, vi a conjectura sendo relacionada com algo sobre b-coloração (um tema para um futuro post), do qual não lembro muito bem como isto era feito.

Confesso que já tentei resolver a conjectura algumas vezes (mais precisamente, cinco vezes). Infelizmente, meus conhecimentos em teoria dos grafos é ainda muito elementar, e o que pude aplicar na conjectura não me retornou nada muito surpreendente (mas ainda sim obtive algumas conclusões).

Cada vez que tentei resolvê-la, esta conjectura me encantava ainda mais. Sim, pois quando eu aprendia algum método novo (como o método probabilístico e o Lema da Regularidade), logo tentava aplicar na conjectura. O interessante é que tais ferramentas eram aplicáveis, em sua maioria, mas o que eu conseguia concluir não era o suficiente para provar a conjectura. É como se a conjectura fosse a prova de métodos fodásticos. Ou até mesmo, eu ainda não sou capaz de aplicá-los de maneira eficiente. Mas também acredito que muitos já devem ter tentado aplicá-los a esta conjectura.

No fim, tentar resolver a conjectura foi um bom exercício para mim. Pretendo mantê-la como um "sonho", e seguindo os conselhos do Bollobás, estudando problemas mais ao meu nível atual.