Filling more gaps on the edge-coloring problem of split graphs - Couto, Fernanda; Ferraz, Diego A.; Figueiredo, Celina M. H. de; Klein, Sulamita (Anais do Encontro de Teoria da Computação (ETC); 2026: Anais do XI Encontro de Teoria da Computação, 2026)
O problema da coloração de arestas é provado ser NP-completo no caso geral. Entretanto, para diversas classes de grafos, este problema permanece em aberto. Uma destas classes é a classe dos grafos split. Recentemente, utilizando uma partição desta classe fornecida pelo problema da t-admissibilidade, classificamos os (σ = 2)-grafos split e uma subclasse dos (σ = 3)-grafos split. Neste trabalho, fazemos uma mudança estratégica em um algoritmo anterior. Tal mudança nos possibilita resolver o problema da coloração de arestas para uma subclasse maior dos (σ = 3)-grafos split.