Atenção:
O eduCAPES é um repositório de objetos educacionais, não sendo responsável por materiais de terceiros submetidos na plataforma. O usuário assume ampla e total responsabilidade quanto à originalidade, à titularidade e ao conteúdo, citações de obras consultadas, referências e outros elementos que fazem parte do material que deseja submeter. Recomendamos que se reporte diretamente ao(s) autor(es), indicando qual parte do material foi considerada imprópria (cite página e parágrafo) e justificando sua denúncia.
Caso seja o autor original de algum material publicado indevidamente ou sem autorização, será necessário que se identifique informando nome completo, CPF e data de nascimento. Caso possua uma decisão judicial para retirada do material, solicitamos que informe o link de acesso ao documento, bem como quaisquer dados necessários ao acesso, no campo abaixo.
Todas as denúncias são sigilosas e sua identidade será preservada. Os campos nome e e-mail são de preenchimento opcional. Porém, ao deixar de informar seu e-mail, um possível retorno será inviabilizado e/ou sua denúncia poderá ser desconsiderada no caso de necessitar de informações complementares.
Metadados | Descrição | Idioma |
---|---|---|
Autor(es): dc.contributor | Almeida, Sheila Morais de | - |
Autor(es): dc.contributor | Almeida, Sheila Morais de | - |
Autor(es): dc.contributor | Groshaus, Marina | - |
Autor(es): dc.contributor | Lima, Alane Marie de | - |
Autor(es): dc.creator | Domingues, Lucas Magalhães | - |
Data de aceite: dc.date.accessioned | 2025-08-29T12:36:44Z | - |
Data de disponibilização: dc.date.available | 2025-08-29T12:36:44Z | - |
Data de envio: dc.date.issued | 2025-06-26 | - |
Data de envio: dc.date.issued | 2025-06-26 | - |
Data de envio: dc.date.issued | 2023-12-06 | - |
Fonte completa do material: dc.identifier | http://repositorio.utfpr.edu.br/jspui/handle/1/37256 | - |
Fonte: dc.identifier.uri | http://educapes.capes.gov.br/handle/capes/1098603 | - |
Descrição: dc.description | A total coloring of a graph is an assignment of colors to its vertices and edges in such a way that any two adjacent vertices have distinct colors, any two edges sharing a vertex have distinct colors, and any vertex has a color different from the colors of the edges incident to it.The Total Coloring Problem is, given a graph 𝐺, to determine the minimum number of colors that allows a total coloring of 𝐺. This number is called the total chromatic number of 𝐺. Given a graph 𝐺 and an integer 𝑘, deciding whether 𝐺 has a total coloring with 𝑘 colors is an NP-complete problem, even when restricted to bipartite graphs. A subclass of bipartite graphs is partial grids. For partial grids, the total chromatic number is known unless the maximum degree of the graph is equal to 3. In this case, there are some partial results.In this work, we reduce the problem of determining the chromatic number of partial grids with a maximum degree of 3 to the problem of determining the chromatic number of biconnected partial grids with a maximum degree of 3, which have chords and whose subgraphs induced by vertices of degree 2 are paths with at most 2 vertices. | - |
Descrição: dc.description | Uma coloração total própria para um grafo é uma atribuição de cores para seus vértices e arestas de forma que quaisquer dois vértices adjacentes tenham cores distintas, quaisquer duas arestas que compartilham vértice tenham cores distintas e qualquer vértice tenha cor diferente da cor das arestas que nele incidem. O Problema da Coloração Total é dado um grafo 𝐺, determinar o menor número de cores que permite uma coloração total de 𝐺. Esse número é chamado de número cromático total de 𝐺. Dado um grafo 𝐺 e um número inteiro 𝑘, decidir 𝐺 tem uma coloração total com 𝑘 cores é um problema NP-completo, mesmo quando restrito aos grafos bipartidos. Uma subclasse dos grafos bipartidos são as grades parciais. Para as grades parciais, o número cromático total é conhecido, a menos que o grau máximo do grafo seja igual a 3. Neste caso, há alguns resultados parciais. Neste trabalho, reduzimos o problema de determinar o número cromático das grades parciais com grau máximo igual a 3 ao problema de determinar o número cromático de grades parciais biconexas com grau máximo 3, que tenham cordas, e cujos subgrafos induzidos por vértices de grau 2 sejam caminhos com no máximo 2 vértices. | - |
Formato: dc.format | application/pdf | - |
Idioma: dc.language | pt_BR | - |
Publicador: dc.publisher | Universidade Tecnológica Federal do Paraná | - |
Publicador: dc.publisher | Ponta Grossa | - |
Publicador: dc.publisher | Brasil | - |
Publicador: dc.publisher | Departamento Acadêmico de Informática | - |
Publicador: dc.publisher | Ciência da Computação | - |
Publicador: dc.publisher | UTFPR | - |
Direitos: dc.rights | openAccess | - |
Direitos: dc.rights | http://creativecommons.org/licenses/by/4.0/ | - |
Palavras-chave: dc.subject | Algorítmos | - |
Palavras-chave: dc.subject | Otimização combinatória | - |
Palavras-chave: dc.subject | Teoria dos grafos | - |
Palavras-chave: dc.subject | Algorithms | - |
Palavras-chave: dc.subject | Combinatorial optimization | - |
Palavras-chave: dc.subject | Graph theory | - |
Palavras-chave: dc.subject | CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO | - |
Título: dc.title | Coloração total em grafos grades parciais | - |
Título: dc.title | Total coloring on partial grid graphs | - |
Tipo de arquivo: dc.type | livro digital | - |
Aparece nas coleções: | Repositorio Institucional da UTFPR - RIUT |
O Portal eduCAPES é oferecido ao usuário, condicionado à aceitação dos termos, condições e avisos contidos aqui e sem modificações. A CAPES poderá modificar o conteúdo ou formato deste site ou acabar com a sua operação ou suas ferramentas a seu critério único e sem aviso prévio. Ao acessar este portal, você, usuário pessoa física ou jurídica, se declara compreender e aceitar as condições aqui estabelecidas, da seguinte forma: