UMA 2022
Una matriz $A \in \{0, 1\}^{n\times m}$ es balanceada [1] si no contiene como submatriz una matriz cuadrada con exactamente dos $1$ por fila y por columna. Un grafo es balanceado [2] si su matriz de incidencia cliques maximales vs. vértices es balanceada. Bonomo, Durán, Lin y Szwarcfiter [5] probaron que un grafo es balanceado si y sólo si no contiene soles impares generalizados como subgrafos inducidos. Sin embargo, esta caracterización no es una caracterización por subgrafos inducidos prohibidos minimales ya que algunos soles impares generalizados contienen otros soles impares generalizados como subgrafos inducidos propios. No se conoce todavía una caracterización por subgrafos inducidos prohibidos minimales de la clase de grafos balanceados. A pesar de esto, existen algunas caracterizaciones parciales en esta dirección.
Un grafo es clique-Helly hereditario (CHH) [9] si todo subgrafo inducido satisface que la intersección de cualquier familia no vacía de cliques maximales que se intersecan dos a dos es no vacía. Todo grafo balanceado es CHH [1]. Un grafo es clique-perfecto si el tamaño máximo de un conjunto independiente de cliques (conjunto de cliques maximales disjuntas dos a dos) y el tamaño mínimo de un conjunto transversal de las cliques (conjunto de vértices que interseca todas las cliques maximales) coinciden para todo subgrafo inducido. Todo grafo balanceado es clique-perfecto [3]. Llamamos claw al grafo bipartito completo $K_{1,3}$. Bonomo, Chudnovsky y Durán [4] probaron que un grafo libre de claw CHH es clique-perfecto si y sólo si no tiene agujeros impares ni antiagujeros de longitud $7$ como subgrafos inducidos.
En nuestro trabajo, probamos que un grafo libre de claw es balanceado si y sólo si es perfecto y CHH o, equivalentemente, si no contiene agujeros impares, antiagujeros de longitud $7$, ni pirámides como subgrafos inducidos. La demostración de este teorema se basa en la caracterización de las descomposiciones por clique-cutsets de los grafos libres de claw perfectos que fue presentada por Chvátal y Sbihi en [6], y refinada por Maffray y Reed en [8], junto con la caracterizacicón de matrices balanceadas por bicoloreos dada por Berge en [1]. Este resultado refina el resultado de Bonomo, Chudnovsky y Durán [4] mostrando que todo grafo libre de claw CHH perfecto no solo es clique-perfecto, sino también balanceado. Como consecuencia de esta caracterización, probamos que existe un algoritmo con complejidad temporal $\mathcal{O}(nm^2)$ que, dado un grafo, determina si es libre de claw balanceado y, en caso que no lo sea, da un certificado de que no lo es. Nuestro algoritmo se basa en el algoritmo de Tarjan [10] para construir una descomposición por clique-cutsets de un grafo dado y el algoritmo de Lin y Szwarcfiter [7] para el reconocimiento de grafos CHH.
Trabajo en conjunto con: Guillermo Durán (Departamento de Matemática, Facultad de Ciencias Exactas y Naturales, Universidad de Buenos Aires (UBA) e Instituto de Cálculo, UBA-CONICET, Buenos Aires, Argentina) y Martín D. Safe (Departamento de Matemática, Universidad Nacional del Sur (UNS) e INMABB, UNS-CONICET, Bahía Blanca, Argentina).
Referencias
[1] C. Berge. “Balanced matrices”. En: Math. Programming 2.1 (1972), págs. 19-31.
[2] C. Berge y V. Chvátal, eds. Topics on perfect graphs. Vol. 88. North-Holland Mathematics Studies. Annals of Discrete Mathematics, 21. North-Holland, Amsterdam, 1984, págs. xiv+369.
[3] C. Berge y M. Las Vergnas. “Sur un théorème du type König pour hypergraphes”. En: Ann. New York Acad. Sci. 175 (1970), págs. 32-40.
[4] F. Bonomo, M. Chudnovsky y G. Durán. “Partial characterizations of clique-perfect graphs. I. Subclasses of claw-free graphs”. En: Discrete Appl. Math. 156.7 (2008), págs. 1058-1082.
[5] F. Bonomo, G. Durán, M. C. Lin y J. L. Szwarcfiter. “On balanced graphs”. En: Math. Program. 105.2-3, Ser. B (2006), págs. 233-250.
[6] V. Chvátal y N. Sbihi. “Recognizing claw-free perfect graphs”. En: J. Combin. Theory Ser. B 44.2 (1988), págs. 154-176.
[7] M. C. Lin y J. L. Szwarcfiter. “Faster recognition of clique-Helly and hereditary clique-Helly graphs”. En: Inform. Process. Lett. 103.1 (2007), págs. 40-43.
[8] F. Maffray y B. A. Reed. “A description of claw-free perfect graphs”. En: J. Combin. Theory Ser. B 75.1 (1999), págs. 134-156.
[9] E. Prisner. “Hereditary clique-Helly graphs”. En: J. Combin. Math. Combin. Comput. 14 (1993), págs. 216-220.
[10] R. E. Tarjan. “Decomposition by clique separators”. En: Discrete Math. 55.2 (1985), págs. 221-232.