Una nueva familia de grafos minimales en [4,2,1]-[3,2,1]

LILIANA ALCÓN; MARISA GUTIERREZ; MARÍA PÍA MAZZOLENI

San Miguel de Tucumán

Congreso; LXI Reunión Anual de Comunicaciones Científicas. 2011; 2011

Una (h,s,t) representación de un grafo G consiste de una colección de subárboles de un árbol T, donde cada subárbol corresponde a un vértice en G tal que: (i) el grado máximo de T es a lo sumo h; (ii) todo subárbol tiene grado máximo a lo sumo s; (iii) existe una arista entre dos vértices en G si y sólo si los subárboles correspondientes tienen al menos t vértices en común en T. La clase de grafos que tiene una (h,s,t) representación es notada [h,s,t].   Algunas clases son conocidas: $[infty,infty,1]$ = Cordales; $[infty,2,2]$ = EPT = UE; $[infty,2,1]$ = VPT = UV = Grafos de Caminos; [2,2,1] = Intervalos.   Estamos interesados en saber qué estructura tienen los grafos G que están en [d,2,1]-[d-1,2,1], con d >3. En este trabajo mostramos un adelanto en este sentido en el caso d=4. Para esto usaremos dos resultados vinculados con la clase EPT: (1) $EPT cap VPT$ = [3,2,1] = [3,2,2]; (2) Si C es un clique de un grafo EPT G entonces el grafo branch B(G/C) es 3-coloreable.   Se sabe que si G tiene Ad, d >3, como subgrafo inducido entonces G no está en [d-1,2,1], con d >3. Por otro lado, Ad es un grafo en [d,2,1]-[d-1,2,1], con d >3, y minimal con esa condición. Nos preguntamos si estos grafos son los únicos minimales en esa diferencia. Encontramos una nueva familia de grafos en [4,2,1]-[3,2,1] minimal con esa condición que incluye a A4.