Grafos Bipartidos Completos em ORTH[3, 3, t]

  • Claudson F. Bornstein
  • José Wilson C. Pinto
  • Jayme L. Szwarcfiter

Resumo


Neste trabalho, nós investigamos sob quais condições um grafo Km,n pertenceá classe ORTH[3, 3, t] introduzida por [Jamison and Mulder 2000]. Mostramos que K4,4 2 / ORTH[3, 3, 4], corroborando uma conjectura de Jamison e Mulder em [Jamison and Mulder 2005]. O principal resultado deste trabalho é a prova da existência de um grafo G ✓ Kn,n e G 2 ORTH[3, 3, 2n 3], se n é uma potência de 2 e n 4.

Publicado
26/07/2018
BORNSTEIN, Claudson F.; PINTO, José Wilson C.; SZWARCFITER, Jayme L.. Grafos Bipartidos Completos em ORTH[3, 3, t]. In: ENCONTRO DE TEORIA DA COMPUTAÇÃO (ETC), 3. , 2018, Natal. Anais [...]. Porto Alegre: Sociedade Brasileira de Computação, 2018 . ISSN 2595-6116. DOI: https://doi.org/10.5753/etc.2018.3167.