Gráfico sin agujeros pares

Gráfico que no contiene ciclos inducidos con un número par de nodos

En el área matemática de la teoría de grafos , una gráfica no tiene huecos 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 gráfico tenga ciclos inducidos de longitud cuatro, o también puede no permitirlos: estos últimos se denominan gráficos libres de ciclos pares . ^[1]

Addario-Berry et al. (2008) demostraron que todo grafo par sin agujeros contiene un vértice bisimplicial (un vértice cuya vecindad es la unión de dos camarillas ), lo que resolvió una conjetura de Reed. Más tarde, Chudnovsky y Seymour (2023) demostraron que la prueba era defectuosa, quienes dieron una prueba correcta.

Reconocimiento

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

Si bien los gráficos sin agujeros pares se pueden reconocer en tiempo polinómico, es NP completo determinar si un gráfico contiene un agujero par que incluye un vértice específico. ^[3]

Se desconoce si la coloración de gráficos y el problema del conjunto independiente máximo se pueden resolver en tiempo polinomial en gráficos libres de agujeros pares, o si son NP-completos. Sin embargo, la camarilla máxima se puede encontrar en gráficos sin agujeros pares en tiempo polinómico. ^[4]

Notas

1. "gráficos libres de ciclo par", www.graphclasses.org , consultado el 12 de marzo de 2023
2. Conforti y col. (2002b) presentan su algoritmo y afirman que se ejecuta en tiempo polinómico sin dar un análisis explícito. Chudnovsky, Kawarabayashi y Seymour (2004) estiman que se ejecuta en "tiempo aproximado ". ${\displaystyle {\mathcal {O}}(n^{40})}$
3. Bienstock (1991)
4. Vušković (2010).

Referencias

• Addario-Berry, Louigi; Chudnovsky, María ; Havet, Federico; Caña, Bruce ; Seymour, Paul (2008), "Vértices bisimpliciales en gráficos libres de agujeros pares", 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 las pruebas de 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), "Gráficos 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), "Gráficos 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 gráficos sin agujeros pares con conjuntos de cortes en estrella y 2 uniones
• Chang, Hsien-Chih; Lu, Hsueh-I (enero de 2012), "Un algoritmo más rápido para reconocer gráficos sin agujeros pares", SODA '12: Actas del vigésimo tercer simposio anual ACM-SIAM sobre algoritmos discretos : 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 gráficos libres de agujeros pares", 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), "Gráficos sin agujeros pares: una encuesta" (PDF) , Análisis aplicable y matemáticas discretas , 4 (2): 219–240, doi :10.2298/AADM100812027V, JSTOR  43666110, SEÑOR  2724633
• Lai, Kai-Yuan; Lu, Hsueh-I; Thorup, Mikkel (2020), "Tres en un árbol en un tiempo casi lineal", en Makarychev, Konstantin; Makarychev, Yuri; Tulsiani, Madhur; Kamath, Gautam; Chuzhoy, Julia (eds.), Actas del 52.º Simposio anual ACM SIGACT sobre teoría de la computación, STOC 2020, Chicago, IL, EE. UU., 22 al 26 de junio de 2020, Association for Computing Machinery, págs. 1279-1292, arXiv : 1909.07446 , doi : 10.1145/3357713.3384235
• Chudnovsky, María; Seymour, Paul (2023), "Los gráficos pares sin agujeros todavía tienen vértices bisimpliciales", Journal of Combinatorial Theory, Serie B , arXiv : 1909.10967 , doi :10.1016/j.jctb.2023.02.009

enlaces externos

• "Gráficos sin agujeros pares", Sistema de Información sobre Clases de Grafos y sus Inclusiones