En la teoría de gráficas, una rama de las matemáticas, una cográfica (en inglés cograph), o gráfica reducible por complementos o gráfica libre de , es una gráfica que puede ser construida recursivamente a partir de la gráfica con un solo vértice por medio de las operaciones unión ajena y complemento. Es decir, la familia de cográficas es la familia más pequeña que contiene a y es cerrada bajo uniones ajenas y complementación.

Las cográficas fueron descubiertas de forma independiente por diversos autores en la década de los años 1970, por ejemplo , , , y mencionan a esta familia. También se les ha llamado -gráficas, gráficas Dacey hereditarias (proveniente del trabajo de James C. Dacey en retículas ortomodulares), y gráficas de 2-paridad. De forma dual a su construcción recursiva, tienen una descomposición estructural simple, usando uniones ajenas y complementos que pueden ser representadas de forma clara y concisa mediante un árbol etiquetado que a su vez es utilizado para resolver algorítmicamente muchos problemas que son computacionalmente difíciles en clases de gráficas más generales, como coloración por vértices o el problema del clan.

La clase de las cográficas contiene a otras familias notables de gráficas, como las gráficas completas, las gráficas multipartitas completas, las gráficas umbral, y sus complementos. A su vez, están contenidas en las familias de gráficas perfectas, gráficas con herencia de distancias, gráficas de permutación, y gráficas de comparabilidad. Definición

Construcción recursiva

Cualquier cográfica puede ser construida recursivamente mediante las siguientes reglas: cualquier gráfica con un solo vértice es una cográfica; si es una cográfica, entonces su complemento también lo es; si y son cográficas, entonces también su unión ajena lo es. Las cográficas son exactamente las gráficas que se pueden construir con estas operaciones. De forma alternativa, en lugar del complemento se puede usar la unión completa de dos cográficas y , que consiste en tomar la uni\'on ajena y agregar una arista entre cada vértice de y cada vértice de .

Otras caracterizationes Existe una amplia lista de caracterizaciones para las cográficas. Entre ellas se tienen: Una cográfica es una gráfica en la que toda subgráfica inducida no trivial tiene al menos dos vértices con las mismas vecindades (abiertas o cerradas). Una cográfica es una gráfica tal que en todas sus subgráficas inducidas, todo clan maximal interseca a todo conjunto independiente maximal en exactamente un vértice. Una cográfica es una gráfica que no contiene a la trayectoria de 4 vértices como subgráfica inducida. Es decir, una gráfica es una cográfica si y sólo si para cualesquiera cuatro de sus vértices , si son aristas de la gráfica, entonces al menos una de , o también es una arista. Una cográfica es una gráfica en la que toda subgráfica inducida conexa y no trivial tiene complemento inconexo. Una cográfica es una gráfica en la que cada subgráfica inducida y conexa tiene diámetro a lo más 2. Una cográfica es una gráfica en la que cada componente conexa es una gráfica con herencia de distancias y diámetro a lo más 2. Una cográfica es una gráfica con clique-width a lo más 2. Una cográfica es la gráfica de comparabilidad de un orden parcial serie-paralelo. Una cográfica es la gráfica de permutación de una permutación separable. Una cográfica es una gráfica en la que toda coloración avariciosa de toda subgráfica inducida usa un número óptimo de colores.

Notas

Referencias

.

Enlaces externos Information System on Graph Class Inclusions: cograph

Categoría:Familias de grafos