Novos resultados sobre coloração de arestas em grafos split: grafos split minimamente 3-admissíveis

• Fernanda Couto UFRRJ
• Diego Amaro Ferraz UFRJ
• Sulamita Klein UFRJ

DOI: https://doi.org/10.5753/etc.2023.229977

Resumo

A classificação dos grafos split quanto à coloração de arestas é um problema em aberto há décadas. Recentemente, utilizamos a partição em subclasses provida pelo PROBLEMA DA t-ADMISSIBILIDADE para grafos split e classificamos grafos split com σ(G) = 2, restando, portanto, classificar os grafos com σ = 3. Neste trabalho, damos um novo passo em direção a esta classificação considerando grafos split com σ = 3 obtidos a partir da adição de um vértice de grau 2 a um grafo split com σ(G) = 2, grafos esses que chamamos de grafos split minimamente 3-admissíveis. Além disso, apresentamos um algoritmo eficiente para a coloração dos grafos que são Classe 1.

Referências

Almeida, S. (2012). Coloração de Arestas em Grafos Split. PhD thesis, Universidade Estadual de Campinas, Instituto de Computação.

Behzad, M., Chartrand, G., e Cooper, J. (1967). The colour numbers of complete graphs. J. London Math. Soc., 42.

Cai, L. e Corneil, D. G. (1995). Tree spanners. SIAM J. Discrete Math., 8:359–387.

Chen, B.-L., Fu, H.-L., e 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. e Cunha, L. (2020). Hardness and efficiency on minimizing maximum distances in spanning trees. Theoretical Computer Science, 838.

Couto, F., Ferraz, D., e Klein, S. (2023). New results on edge-coloring and total-coloring of split graphs. Discrete Applied Mathematics: Notes. Submetido.

Garey, M. R. e Johnson, D. S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness (Series of Books in the Mathematical Sciences). W. H. Freeman, first edition edition.

Gonzaga, L. (2021). Coloração de arestas em grafos split-comparabilidade e split-intervalos. Master’s thesis, Universidade Estadual de Campinas, Instituto de Computação.

Holyer, I. (1981). The np-completeness of edge-coloring. SIAM J. Comput., 10:718–720.

Johnson, D. S. (1987). The np-completeness column: An ongoing guide. Journal of Algorithms, 8(3):438–448.

Ortiz, C., Maculan, N., e Szwarcfiter, J. L. (1998). Characterizing and edge-colouring split-indifference graphs. Discrete Applied Mathematics, 82(1):209–217.

Plantholt, M. (1981). The chromatic index of graphs with a spanning star. J. 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.