• Login
    View Item 
    •   DSpace Home
    • BIBLIOTECA DIGITAL: Teses & Dissertações
    • 40001016034P5 Programa de Pós-Graduação em Informática
    • Dissertações
    • View Item
    •   DSpace Home
    • BIBLIOTECA DIGITAL: Teses & Dissertações
    • 40001016034P5 Programa de Pós-Graduação em Informática
    • Dissertações
    • View Item
    JavaScript is disabled for your browser. Some features of this site may not work without it.

    Homomorfismos para coloração de grafos

    Thumbnail
    View/Open
    R - D - JOAO PEDRO WINCKLER BERNARDI.pdf (1.487Mb)
    Date
    2019
    Author
    Bernardi, João Pedro Winckler
    Metadata
    Show full item record
    Subject
    Homomorfismos (Matemática)
    Álgebra homológica
    Ciência da Computação
    xmlui.dri2xhtml.METS-1.0.item-type
    Dissertação Digital
    Abstract
    Resumo: A famosa tabela de problemas NP-completos de D. Johnson de 1985 relaciona problemas NP-completos com classes de grafos. Uma entrada da tabela representa a complexidade de um problema para determinada classe de grafo. Desde que foi feita pela primeira vez, a entrada para o Problema de Coloração de Arestas com a classe dos grafos cordais permanece vazia, pois ainda é um problema indeterminado. Uma conjectura de Figueiredo, Meidanis, e Mello da década de 90 diz que todo grafo cordal com grau máximo ímpar tem seu índice cromático igual ao grau máximo do grafo. Com o estudo do problema, foi desenvolvida a técnica pullback para colorir um subconjunto os grafos de intervalos, uma subclasse dos grafos cordais. Nosso trabalho generaliza a pullback para colorir um subconjunto dos grafos arco-circulares próprios ? cordais, uma superclasse dos grafos de intervalos próprios. Palavras-chave: Pullback. Coloração de arestas. Coloração total.
     
    Abstract: Each entry from the famous D. Johnson's NP-completeness column of 1985 represents the complexity of a problem for a given graph class. Since it was first made, the entry for the Edge Coloring Problem with chordal graphs remains empty, as it is still undetermined. A conjecture by Figueiredo, Meidanis, and Mello, open since late 1990s, states that every chordal graph with odd maximum degree has its chromatic index equal to the maximum degree of the graph. With the study of the problem, the technique pullback was developed to color a subset of interval graphs, a subclass of chordal graphs. Our work generalizes the pullback to color a subset of proper circular arc ? chordals graphs, a superclass of the proper interval graphs. Keywords: Pullback. Edge-coloring. Total coloring.
     
    URI
    https://hdl.handle.net/1884/67798
    Collections
    • Dissertações [348]

    DSpace software copyright © 2002-2016  DuraSpace
    Contact Us | Send Feedback
    Theme by 
    Atmire NV
     

     

    Browse

    All of DSpaceCommunities & CollectionsBy Issue DateAuthorsTitlesSubjectsxmlui.ArtifactBrowser.Navigation.browse_typeThis CollectionBy Issue DateAuthorsTitlesSubjectsxmlui.ArtifactBrowser.Navigation.browse_type

    My Account

    LoginRegister

    Statistics

    View Usage Statistics

    DSpace software copyright © 2002-2016  DuraSpace
    Contact Us | Send Feedback
    Theme by 
    Atmire NV