Gráfico sin agujeros pares

En el ámbito matemático de la teoría de grafos , un grafo es libre de agujeros pares si no contiene ningún ciclo inducido con un número par de vértices . Más precisamente, la definición puede permitir que el grafo tenga ciclos inducidos de longitud cuatro, o también puede prohibirlos: a estos últimos se les denomina grafos libres de ciclos pares . ^{[ 1 ]}

Addario-Berry et al. (2008) demostraron que todo grafo par sin ciclos contiene un vértice bisimplicial (un vértice cuyo vecindario es la unión de dos cliques ), lo que resolvió una conjetura de Reed. Posteriormente, Chudnovsky y Seymour (2023) demostraron que la prueba era errónea y proporcionaron una demostración correcta.

Conforti et al. (2002b) dieron el primer algoritmo de reconocimiento de tiempo polinomial para grafos pares sin agujeros, que se ejecuta en${\displaystyle {\mathcal {O}}(n^{40})}$tiempo. ^{[ 2 ]} da Silva y Vušković (2008) posteriormente mejoraron esto a${\displaystyle {\mathcal {O}}(n^{19})}$Chang y Lu (2012) y Chang y Lu ( 2015) mejoraron esto a${\displaystyle {\mathcal {O}}(n^{11})}$tiempo. El mejor algoritmo conocido actualmente es el proporcionado por Lai, Lu y Thorup (2020) , que se ejecuta en${\displaystyle {\mathcal {O}}(n^{9})}$tiempo.

Aunque los grafos sin agujeros pares se pueden reconocer en tiempo polinomial, determinar si un grafo contiene un agujero par que incluye un vértice específico es un problema NP -completo. ^{[ 3 ]}

Se desconoce si la coloración de grafos y el problema del conjunto independiente máximo pueden resolverse en tiempo polinomial en grafos sin agujeros pares, o si son problemas NP-completos. Sin embargo, la camarilla máxima puede hallarse en grafos sin agujeros pares en tiempo polinomial. ^{[ 4 ]}

• Addario-Berry, Louigi; Chudnovsky, Maria ; Havet, Frédéric; Reed, Bruce ; Seymour, Paul (2008), "Vértices bisimpliciales en grafos pares sin agujeros", Journal of Combinatorial Theory , Serie B, 98 (6): 1119–1164 , doi : 10.1016/j.jctb.2007.12.006
• Bienstock, Dan (1991), "Sobre la complejidad de probar agujeros impares y caminos impares inducidos", Matemáticas Discretas , 90 (1): 85– 92, doi : 10.1016/0012-365X(91)90098-M
• Chudnovsky, María ; Kawarabayashi, Ken-ichi ; Seymour, Paul (2004), "Detección de agujeros pares", Journal of Graph Theory , 48 (2): 85– 111, doi : 10.1002/jgt.20040 , S2CID 2945499 
• Conforti, Michele; Cornuéjols, Gérard ; Kapoor, Ajai; Vušković, Kristina (enero de 2002a), "Grafos pares sin agujeros, parte I: Teorema de descomposición" (PDF) , Journal of Graph Theory , 39 (1): 6–49 , doi : 10.1002/jgt.10006 , S2CID 12947855 
• Conforti, Michele; Cornuéjols, Gérard ; Kapoor, Ajai; Vušković, Kristina (agosto de 2002b), "Grafos sin agujeros pares, parte II: algoritmo de reconocimiento" (PDF) , Journal of Graph Theory , 40 (4): 238–266 , doi : 10.1002/jgt.10045 , S2CID 15044085 
• da Silva, Murilo VG; Vušković, Kristina (2008), Descomposición de grafos pares sin agujeros con conjuntos de corte estrella y 2-uniones
• Chang, Hsien-Chih; Lu, Hsueh-I (enero de 2012), "Un algoritmo más rápido para reconocer grafos pares sin agujeros", Actas del vigésimo tercer simposio anual ACM-SIAM sobre algoritmos discretos , págs. 1286–1297 , arXiv : 1311.0358 , doi : 10.1137/1.9781611973099.101 , ISBN  978-1-61197-210-8
• Chang, Hsien-Chih; Lu, Hsueh-I (julio de 2015), "Un algoritmo más rápido para reconocer grafos pares sin agujeros", Journal of Combinatorial Theory, Serie B , 113 : 141–161 , arXiv : 1311.0358 , doi : 10.1016/j.jctb.2015.02.001 , S2CID 1744497 
• Vušković, Kristina (2010), "Grafos pares sin agujeros: una revisión" (PDF) , Applicable Analysis and Discrete Mathematics , 4 (2): 219– 240, doi : 10.2298/AADM100812027V , JSTOR 43666110 , MR 2724633  
• Lai, Kai-Yuan; Lu, Hsueh-I; Thorup, Mikkel (2020), "Three-in-a-tree in near linear time", en Makarychev, Konstantin; Makarychev, Yury; Tulsiani, Madhur; Kamath, Gautam; Chuzhoy, Julia (eds.), Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020, Chicago, IL, USA, June 22–26, 2020 , Association for Computing Machinery, pp. 1279– 1292, arXiv : 1909.07446 , doi : 10.1145/3357713.3384235 , ISBN  978-1-4503-6979-4
• Chudnovsky, Maria; Seymour, Paul (2023), "Los grafos sin agujeros pares aún tienen vértices bisimpliciales" , Journal of Combinatorial Theory, Series B , 161 : 331–381 , arXiv : 1909.10967 , doi : 10.1016/j.jctb.2023.02.009

• "Grafos sin agujeros pares" , Sistema de información sobre clases de grafos y sus inclusiones