Filling more gaps on the edge-coloring problem of split graphs
Resumo
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.
Referências
Behzad, M., Chartrand, G., and Cooper, J. (1967). The colour numbers of complete graphs. Journal of the London Mathematical Society, 42.
Cai, L. and Corneil, D. G. (1995). Tree spanners. SIAM Journal on Discrete Mathematics, 8:359–387.
Chen, B.-L., Fu, H.-L., and Ko, M.-T. (1995). Total chromatic number and chromatic index of split graphs. JCMCC. The Journal of Combinatorial Mathematics and Combinatorial Computing, 17.
Couto, F., Ferraz, D. A., and Klein, S. (2025). New results on edge-coloring and total-coloring of split graphs. Discrete Applied Mathematics, 360:297–306.
Couto, F., Ferraz, D. A., and Klein, S. (2026). Filling some gaps on the edge coloring problem of split graphs. Discrete Applied Mathematics, 380:420–430.
da Soledade Gonzaga, L. G., de Sousa Cruz, J. B., de Almeida, S. M., and da Silva, C. N. (2023). The overfull conjecture on split-comparability and split-interval graphs. Discrete Applied Mathematics, 340:228–238.
de Figueiredo, C. M., Meidanis, J., and de Mello, C. P. (1999). Total-chromatic number and chromatic index of dually chordal graphs. Information Processing Letters, 70(3):147–152.
Holyer, I. (1981). The NP-completeness of edge-coloring. SIAM Journal on Computing, 10:718–720.
Konig, D. (1916). Uber graphen und ihre anwendung auf determinantentheorie und mengenlehre. Mathematische Annalen, 77:453–465.
Panda, B. and Das, A. (2010). Tree 3-spanners in 2-sep chordal graphs: Characterization and algorithms. Discrete Applied Mathematics, 158:1913–1935.
Plantholt, M. (1981). The chromatic index of graphs with a spanning star. Journal of Graph Theory, 5:45–53.
Vizing, V. (1964). On an estimate of the chromatic class of a p-graph (in russian). (Russian) Diskret Analiz, 3.
Cai, L. and Corneil, D. G. (1995). Tree spanners. SIAM Journal on Discrete Mathematics, 8:359–387.
Chen, B.-L., Fu, H.-L., and Ko, M.-T. (1995). Total chromatic number and chromatic index of split graphs. JCMCC. The Journal of Combinatorial Mathematics and Combinatorial Computing, 17.
Couto, F., Ferraz, D. A., and Klein, S. (2025). New results on edge-coloring and total-coloring of split graphs. Discrete Applied Mathematics, 360:297–306.
Couto, F., Ferraz, D. A., and Klein, S. (2026). Filling some gaps on the edge coloring problem of split graphs. Discrete Applied Mathematics, 380:420–430.
da Soledade Gonzaga, L. G., de Sousa Cruz, J. B., de Almeida, S. M., and da Silva, C. N. (2023). The overfull conjecture on split-comparability and split-interval graphs. Discrete Applied Mathematics, 340:228–238.
de Figueiredo, C. M., Meidanis, J., and de Mello, C. P. (1999). Total-chromatic number and chromatic index of dually chordal graphs. Information Processing Letters, 70(3):147–152.
Holyer, I. (1981). The NP-completeness of edge-coloring. SIAM Journal on Computing, 10:718–720.
Konig, D. (1916). Uber graphen und ihre anwendung auf determinantentheorie und mengenlehre. Mathematische Annalen, 77:453–465.
Panda, B. and Das, A. (2010). Tree 3-spanners in 2-sep chordal graphs: Characterization and algorithms. Discrete Applied Mathematics, 158:1913–1935.
Plantholt, M. (1981). The chromatic index of graphs with a spanning star. Journal of Graph Theory, 5:45–53.
Vizing, V. (1964). On an estimate of the chromatic class of a p-graph (in russian). (Russian) Diskret Analiz, 3.
Publicado
19/07/2026
Como Citar
COUTO, Fernanda; FERRAZ, Diego A.; FIGUEIREDO, Celina M. H. de; KLEIN, Sulamita.
Filling more gaps on the edge-coloring problem of split graphs. In: ENCONTRO DE TEORIA DA COMPUTAÇÃO (ETC), 11. , 2026, Gramado/RS.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2026
.
p. 133-138.
ISSN 2595-6116.
DOI: https://doi.org/10.5753/etc.2026.22134.
