Sesión Matemática DiscretaHacia una caracterización de los grafos balanceados dentro de la clase de grafos coclaw-free
Lucía Busolini
Universidad de Buenos Aires, Argentina - Esta dirección de correo electrónico está siendo protegida contra los robots de spam. Necesita tener JavaScript habilitado para poder verlo.
Una matriz $A \in \{0,1\}^{n\times m}$ es balanceada [1] si no contiene como submatriz una matriz cuadrada de orden impar con exactamente dos 1’s por fila y por columna. Un grafo $G$ es balanceado [2] si su matriz de incidencia cliques maximales vs. vértices es balanceada. Bonomo, Durán, Lin y Szwarcfiter probaron en [3] 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.
Anteriormente, logramos caracterizar los grafos claw-free (es decir, que no tienen $K_{1,3}$ inducidos) que son balanceados, como aquellos que no contienen agujeros impares, antiagujeros de longitud 7, ni pirámides como subgrafos inducidos. Notamos que los resultados previos [1, 4, 5] que usamos para esta caracterización pueden aplicarse también en el caso de grafos coclaw-free (es decir, que no tienen $K_3 \cup K_1$ inducidos), y es por esto que estamos trabajando en la caracterización de los grafos coclaw-free que son balanceados.
En esta charla voy a introducir los trabajos previos que fueron la base para lograr describir los grafos claw-free balanceados. Además, mencionaré qué nos permite afirmar acerca de los grafos coclaw-free que son balanceados y los resultados parciales que hemos obtenido en el camino a una caracterización por subgrafos inducidos prohibido minimales de los grafos coclaw-free que son balanceados.
Trabajo en conjunto con: Guillermo Durán (Universidad de Buenos Aires, Argentina) y Martín D. Safe (Universidad Nacional del Sur, 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] 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.
[4] V. Chvátal y N. Sbihi. “Recognizing claw-free perfect graphs”. En: J. Combin. Theory Ser. B 44.2 (1988), págs. 154-176.
[5] 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. 1