Use este identificador para citar ou linkar para este item: http://repositorio.utfpr.edu.br/jspui/handle/1/33246
Registro completo de metadados
Campo DCValorIdioma
dc.creatorMontanheiro, Gustavo Leardini-
dc.date.accessioned2024-02-01T16:35:19Z-
dc.date.available2024-02-01T16:35:19Z-
dc.date.issued2022-12-16-
dc.identifier.citationMONTANHEIRO, Gustavo Leardini. Caracterização e coloração total de grafos bipartidos com até três bicliques. 2022. Trabalho de Conclusão de Curso de (Bacharelado em Engenharia de Computação) - Universidade Tecnológica Federal do Paraná, Curitiba, 2022.pt_BR
dc.identifier.urihttp://repositorio.utfpr.edu.br/jspui/handle/1/33246-
dc.description.abstractThe total chromatic number of a graph 𝐺 is the least number of colours necessary to colour all the vertices and edges of 𝐺 só that no adjacent elements have the same colour. Determining the total chromatic number of a graph is an important hard problem that has been studied for many graph classes, including graphs with few cliques. For graphs with a universal vertex, it was solved by Hilton in 1990. If the total chromatic number of a graph 𝐺 is ∆(𝐺) + 1, 𝐺 is said to be Type 1. If it is ∆(𝐺) + 2, then 𝐺 is Type 2. In 2012, Campos et al. solved the problem for split-indifference graphs, all of which have at most three cliques, proving that such a graph 𝐺 is: Type 2 if 𝐺 has some ∆-subgraph 𝐻 (i.e a subgraph with ∆(𝐻) = ∆(𝐺)) which has a universal vertex and is Type 2; Type 1 otherwise. In 1991, Hilton also solved the problem for bipartite graphs with adjacent bi-universal vertices (a vertex in a part of a bipartite graph is bi-universal if it is adjacent to all vertices in the other part). We conjecture that a bipartite graph 𝐺 with at most three bicliques is: Type 2 if 𝐺 has some Type 2 ∆-subgraph with adjacent bi-universal vertices; Type 1 otherwise. If 𝐺 has at most two bicliques, then the conjecture holds by Hilton’s result. If 𝐺 has three bicliques, we prove that the graph obtained after successively removing twins is either a 𝑃5 or has adjacent bi-universal vertices. For the former case, let 𝐴, 𝐵, 𝐶, 𝐷, 𝐸 be the sets of twin vertices, where the 𝑃5 is given by the sequence 𝐴𝐵𝐶𝐷𝐸, being 𝑎, 𝑏, 𝑐, 𝑑, 𝑒 their corresponding cardinalities, with 𝑎 ≥ 𝑒 without loss of generality. Then, we prove that our conjecture holds for all the following cases: 𝑏 + 𝑑 ̸= 𝑐 + 𝑎; 𝑏 + 𝑑 = 𝑐 + 𝑎 > 𝑎𝑑 + min(𝑎, 𝑑); max(𝑑, 𝑒) < 𝑎 and 𝑎𝑑 ≥ 𝑏. So, the conjecture remains open when 𝑏 + 𝑑 = 𝑐 + 𝑎 ≤ 𝑎𝑑 + min(𝑎, 𝑑) and: either 𝑑 ≥ 𝑎, or 𝑎 = 𝑒 > 𝑑.pt_BR
dc.languageporpt_BR
dc.publisherUniversidade Tecnológica Federal do Paranápt_BR
dc.rightsopenAccesspt_BR
dc.rights.urihttp://creativecommons.org/licenses/by/4.0/pt_BR
dc.subjectTeoria dos grafospt_BR
dc.subjectGrafos bipartidospt_BR
dc.subjectColoração de grafospt_BR
dc.subjectGraph theorypt_BR
dc.subjectBipartite graphspt_BR
dc.subjectGraph coloringpt_BR
dc.titleCaracterização e coloração total de grafos bipartidos com até três bicliquespt_BR
dc.title.alternativeCharacterising and total colouring bipartite graphs with at most three bicliquespt_BR
dc.typebachelorThesispt_BR
dc.description.resumoO número cromático total de um grafo 𝐺 é o menor número de cores necessário para colorir todos os vértices e todas as arestas de 𝐺 de modo que não haja cores iguais em elementos adjacentes. Determinar o número cromático total de um grafo é um problema importante, porém difícil, que já foi estudado em diversas classes de grafos, incluindo grafos com poucas cliques. Para grafos com um vértice universal, o problema foi resolvido por Hilton em 1990. Se o número cromático total de um grafo 𝐺 é ∆(𝐺) + 1, dizemos que 𝐺 é Tipo 1. Se é ∆(𝐺) + 2, dizemos que 𝐺 é Tipo 2. Em 2012, Campos et al. determinaram o número cromático total dos grafos split-indiferença, os quais contêm no máximo três cliques, provando que 𝐺 é Tipo 2 se 𝐺 tem um ∆-subgrafo 𝐻 que tem um vértice universal e é Tipo 2; senão é Tipo 1. Em 1991, Hilton também resolveu o problema para grafos bipartidos com vértices biuniversais adjacentes. Nós conjecturamos que um grafo bipartido 𝐺 com no máximo três bicliques é: Tipo 2 se 𝐺 tem algum ∆-subgrafo Tipo 2 com vértices biuniversais adjacentes; senão é Tipo 1. Se 𝐺 tem no máximo duas bicliques, então a conjectura vale pelo resultado de Hilton. Se 𝐺 tem três bicliques, nós provamos que o grafo obtido após a remoção sucessiva de vértices falsos gêmeos é isomorfo ao 𝑃5 ou tem vértices biuniversais adjacentes. No primeiro caso, sejam 𝐴, 𝐵, 𝐶, 𝐷, 𝐸 os conjuntos de vértices falsos gêmeos de 𝐺, onde o 𝑃5 é dado pela sequência 𝐴𝐵𝐶𝐷𝐸, com 𝑎, 𝑏, 𝑐, 𝑑, 𝑒 sendo suas respectivas cardinalidades, com 𝑎 ≥ 𝑒 sem perda de generalidade. Então, provamos que nossa conjectura vale para todos os seguintes casos: 𝑏 + 𝑑 ̸= 𝑐 + 𝑎; 𝑏 + 𝑑 = 𝑐 + 𝑎 > 𝑎𝑑+ min(𝑎, 𝑑); max(𝑑, 𝑒) < 𝑎 e 𝑎𝑑 ≥ 𝑏. A conjectura permanece aberta para os casos em que 𝑏 + 𝑑 = 𝑐 + 𝑎 ≤ 𝑎𝑑 + min(𝑎, 𝑑) e: ou 𝑑 ≥ 𝑎, ou 𝑎 = 𝑒 > 𝑑.pt_BR
dc.degree.localCuritibapt_BR
dc.publisher.localCuritibapt_BR
dc.contributor.advisor1Zatesko, Leandro Miranda-
dc.contributor.advisor-co1Groshaus, Marina Esther-
dc.contributor.referee1Zatesko, Leandro Miranda-
dc.contributor.referee2Groshaus, Marina Esther-
dc.contributor.referee3Rocha, Aleffer-
dc.contributor.referee4Almeida, Sheila Morais de-
dc.publisher.countryBrasilpt_BR
dc.publisher.programEngenharia de Computaçãopt_BR
dc.publisher.initialsUTFPRpt_BR
dc.subject.cnpqCNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAOpt_BR
Aparece nas coleções:CT - Engenharia de Computação

Arquivos associados a este item:
Arquivo Descrição TamanhoFormato 
bicliques.pdf285,51 kBAdobe PDFThumbnail
Visualizar/Abrir


Este item está licenciada sob uma Licença Creative Commons Creative Commons