Data: 11/03/2021, às 16:00 horas (GMT-3, horário de Brasília).
Título: Coloração de arestas em grafos split: o que sabemos após 35 anos da coluna de Johnson
Palestrante: Sheila Almeida (UTFPR)


Resumo: Em setembro de 1985 David Johnson publicou a 6a edição de sua coluna trimestral "The NP-completeness column: an ongoing guide". Nesta edição dedicou-se a apresentar problemas conhecidos da Teoria dos Grafos e falar sobre a complexidade computacional destes quando restritos a classes de grafos relevantes do ponto de vista algorítmico. Dentre os onze problemas discutidos, os dois que mais se destacaram naquela edição pelo número de classes para as quais a complexidade de tempo era desconhecida foram o Problema do Corte Máximo e o Problema da Coloração de Arestas. Este último tinha complexidade desconhecida em vinte e duas das trinta classes de grafos apresentadas. Em duas destas classes, Johnson disse que o Problema da Coloração de Arestas aparentemente poderia ser resolvido por técnicas conhecidas, mas que ainda não havia checado os detalhes. Para outras dezenove classes, Johnson disse que a determinação da complexidade deste problema aparentemente estava em aberto, mas que era possivelmente fácil de se determinar. Trinta e cinco anos depois, o Problema da Coloração de Arestas ainda tem complexidade desconhecida para catorze destas classes e provou-se NP-completo para quatro delas. Entre as catorze classes para as quais a complexidade permanece em aberto estão as dos grafos split e dos grafos de intervalos. Dentre as classes para as quais o problema mostrou-se NP-completo está a dos grafos de comparabilidade. Vamos apresentar o que se sabe sobre o Problema da Coloração de Arestas em grafos split 35 anos depois. E discutir os resultados que garantem que este problema é polinomial quando restrito às interseções split-comparabilidade e split-intervalos.