Gráfica de paridad

En teoría de grafos , un grafo de paridad es un grafo en el que cada dos caminos inducidos entre los mismos dos vértices tienen la misma paridad : o ambos caminos tienen una longitud impar, o ambos tienen una longitud par. ^[1] Esta clase de grafos fue nombrada y estudiada por primera vez por Burlet y Uhry (1984). ^[2]

Los grafos de paridad incluyen los grafos hereditarios de distancia , en los que cada dos caminos inducidos entre los mismos dos vértices tienen la misma longitud. También incluyen los grafos bipartitos , que pueden caracterizarse de manera análoga como los grafos en los que cada dos caminos (no necesariamente caminos inducidos) entre los mismos dos vértices tienen la misma paridad, y los grafos de línea perfecta , una generalización de los grafos bipartitos. Cada grafo de paridad es un grafo de Meyniel , un grafo en el que cada ciclo impar de longitud cinco o más tiene dos cuerdas. Porque, en un grafo de paridad, cualquier ciclo impar largo se puede dividir en dos caminos de diferentes paridades, ninguno de los cuales es una arista única, y se necesita al menos una cuerda para evitar que ambos sean caminos inducidos. Luego, al dividir el ciclo en dos caminos entre los puntos finales de esta primera cuerda, se necesita una segunda cuerda para evitar que se induzcan los dos caminos de esta segunda partición. Como los grafos de Meyniel son grafos perfectos , los grafos de paridad también son perfectos. ^[1] Son exactamente los grafos cuyo producto cartesiano con una sola arista permanece perfecto. ^[3]

Un grafo es un grafo de paridad si y solo si cada componente de su descomposición dividida es un grafo completo o un grafo bipartito . ^[4] Con base en esta caracterización, es posible probar si un grafo dado es un grafo de paridad en tiempo lineal . La misma caracterización también conduce a generalizaciones de algunos algoritmos de optimización de grafos desde grafos bipartitos a grafos de paridad. Por ejemplo, utilizando la descomposición dividida, es posible encontrar el conjunto independiente máximo ponderado de un grafo de paridad en tiempo polinomial . ^[5]