Uma conjectura de Erdos e Hajnal (2023)
- Authors:
- Autor USP: ENJU, RODRIGO APARECIDO - IME
- Unidade: IME
- Sigla do Departamento: MAC
- DOI: 10.11606/D.45.2023.tde-15032023-190119
- Assunto: TEORIA DA COMPUTAÇÃO
- Keywords: Chromatic number; Cintura; Girth; Grafo de Kneser; Kneser graph; Número cromático; Shift graph; Type graph
- Agências de fomento:
- Language: Português
- Abstract: Um resultado de Erdos demonstra a existência de grafos com número cromático e cintura arbitrariamente grandes. Temos então que um clique suficientemente grande contém um grafo com número cromático e cintura grandes como subgrafo, porém muitos grafos de interesse não necessariamente contém cliques grandes, então é interessante encontrar outra condição que garanta a existência de subgrafos com número cromático e cintura grandes. Uma conjectura de Erdos e Hajnal diz que todo grafo com número cromático suficientemente grande contém um subgrafo com número cromático e cintura grandes. O objetivo deste trabalho é estudar tal conjectura. O texto começa com uma breve apresentação de construções livres de triângulos. Em particular, é demonstrada uma construção de Codenotti, Pudlák e Resta, por meio de planos projetivos. O tópico principal do texto começa com uma demonstração de Rödl de que todo grafo com número cromático suficientemente grande contém um subgrafo livre de triângulos e com número cromático grande. Em sequência, apresentaremos uma demonstração de que grafos com número cromático suficientemente grande contém algum circuito ímpar grande. Apresentaremos também um resultado de Mohar e Wu, que demonstra que a família dos grafos de Kneser respeita a conjectura de Erdos e Hajnal. Outro resultado apresentado é de Gábor Tardos, demonstrando que a família dos shift graphs respeita a conjectura de Erdos e Hajnal.E por fim apresentaremos alguns breves resultados sobre os type graphs, mostrando casos que respeitam a conjectura de Erdos e Hajnal
- Imprenta:
- Data da defesa: 31.01.2023
- Este periódico é de acesso aberto
- Este artigo NÃO é de acesso aberto
-
ABNT
ENJU, Rodrigo Aparecido. Uma conjectura de Erdos e Hajnal. 2023. Dissertação (Mestrado) – Universidade de São Paulo, São Paulo, 2023. Disponível em: https://www.teses.usp.br/teses/disponiveis/45/45134/tde-15032023-190119/. Acesso em: 16 fev. 2026. -
APA
Enju, R. A. (2023). Uma conjectura de Erdos e Hajnal (Dissertação (Mestrado). Universidade de São Paulo, São Paulo. Recuperado de https://www.teses.usp.br/teses/disponiveis/45/45134/tde-15032023-190119/ -
NLM
Enju RA. Uma conjectura de Erdos e Hajnal [Internet]. 2023 ;[citado 2026 fev. 16 ] Available from: https://www.teses.usp.br/teses/disponiveis/45/45134/tde-15032023-190119/ -
Vancouver
Enju RA. Uma conjectura de Erdos e Hajnal [Internet]. 2023 ;[citado 2026 fev. 16 ] Available from: https://www.teses.usp.br/teses/disponiveis/45/45134/tde-15032023-190119/
Informações sobre o DOI: 10.11606/D.45.2023.tde-15032023-190119 (Fonte: oaDOI API)
How to cite
A citação é gerada automaticamente e pode não estar totalmente de acordo com as normas
