Sesión Matemática Discreta

Grafos sin triángulos cuyo cuadrado de línea no tiene agujeros de longitud al menos $k$

Martina Vergara

Departamento de Matemática, UNS e INMABB, UNS-CONICET, Argentina   -   Esta dirección de correo electrónico está siendo protegida contra los robots de spam. Necesita tener JavaScript habilitado para poder verlo.

El grafo de línea de un grafo $G$, denotado $L(G)$, tiene un vértice por cada arista de $G$ y dos vértices de $L(G)$ son adyacentes si y solo si corresponden a aristas que comparten un extremo. El cuadrado de un grafo $G$, denotado $G^2$, tiene los mismos vértices que $G$ y dos vértices de $G^2$ son adyacentes si y solo si están unidos en $G$ por un camino de longitud a lo sumo $2$. El cuadrado de línea de un grafo $G$ es el cuadrado del grafo de línea de $G$, es decir, $L(G)^2$. Denotamos por $C_k$ al ciclo sin cuerdas con $k$ vértices. Decimos que $C_k$ es un agujero si $k\geq 4$. Un grafo es libre de $C_k$ si no contiene $C_k$ como subgrafo inducido. Un grafo es libre de $C_{\geq k}$ si es libre de $C_t$, para todo $t\geq k$.

Dos aristas se dicen independientes si no comparten extremos ni son ambas incidentes a una arista en común. El problema del Matching Inducido Máximo (MIM) consiste en encontrar un conjunto de aristas independientes dos a dos de máxima cardinalidad. El problema del Conjunto Independiente Máximo (CIM) consiste en hallar un conjunto de vértices no adyacentes dos a dos de máxima cardinalidad. Claramente, resolver MIM en un grafo $G$ es equivalente a resolver CIM en $L(G)^2$. Este hecho implica que MIM puede resolverse en tiempo polinomial (resp. cuasipolinomial) en la clase de todos los grafos $G$ tales que $L(G)^2\in\mathcal H$, para cada clase $\mathcal H$ de grafos en la cual CIM puede resolverse en tiempo polinomial (resp. cuasipolinomial).

En particular, se sabe que CIM se puede resolver en tiempo polinomial en la clase de los grafos libres de $C_{\geq 5}$ [1] y en tiempo cuasipolinomial en la clase de los grafos libres de $C_{\geq k}$, para cada $k$ [2]. Por lo tanto, si $\mathcal{G}_{\geq k}$ es la clase de los grafos $G$ tales que $L(G)^2$ es libre de $C_{\geq k}$ entonces MIM se puede resolver en tiempo polinomial en $\mathcal{G}_{\geq 5}$ y en tiempo cuasipolinomial en $\mathcal{G}_{\geq k}$, para cada $k$, respectivamente.

Scheidweiler y Wiederrecht [3] caracterizaron la clase de los grafos cuyo cuadrado de línea es libre de $C_k$, para cada $k\geq 4$. A partir de dicha caracterización, en particular, hallaron la familia de subgrafos inducidos prohibidos para la clase de los grafos cuyo cuadrado de línea es cordal, esto es, para $\mathcal{G}_{\geq 4}$. Sin embargo, ninguna de estas caracterizaciones es por subgrafos inducidos prohibidos minimales, pues algunos de los subgrafos prohibidos contienen a otros como subgrafos inducidos propios.

Adaptando métodos que desarrollamos en un trabajo previo sobre cuadrados de línea libres de caminos sin cuerdas, en esta comunicación presentamos una caracterización por subgrafos inducidos prohibidos minimales de la clase de los grafos sin triángulos cuyo cuadrado de línea es libre de $C_{\geq k}$, para cada $k\geq 4$. Cada familia de subgrafos inducidos prohibidos minimales queda caracterizada mediante un conjunto de cadenas aceptadas por un autómata finito determinista.

* Este trabajo fue financiado parcialmente por los subsidios PGI 24/L115 y 24/L133 de la Universidad Nacional del Sur. M.D. Safe fue financiado parcialmente por el subsidio PIBAA 28720210101185CO del CONICET.

Trabajo en conjunto con: Martín D. Safe (Departamento de Matemática, UNS e INMABB, UNS-CONICET).

Referencias

[1] T. Abrishami, M. Chudnovsky, M. Pilipczuk, P. Rzążewski, and P. Seymour. Induced subgraphs of bounded treewidth and the container method. SIAM J. Comput., 53(3):624–647, 2024.

[2] P. Gartland, D. Lokshtanov, M. Pilipczuk, M. Pilipczuk, and P. Rzążewski. Finding large induced sparse subgraphs in $C_{>t}$-free graphs in quasipolynomial time. In STOC ’21—Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, pages 330–341. ACM, New York, 2021.

[3] R. Scheidweiler and S. Wiederrecht. On chordal graph and line graph squares. Discrete Appl. Math., 243:239–247, 2018.

Ver resumen en PDF