En el área matemática de la teoría de grafos , un grafo bipartito cordal es un grafo bipartito B = ( X , Y , E ) en el que cada ciclo de longitud al menos 6 en B tiene una cuerda , es decir, una arista que conecta dos vértices que están una distancia > 1 entre sí en el ciclo. [1] Un mejor nombre sería débilmente cordal y bipartito ya que los grafos cordales bipartitos en general no son cordales como muestra el ciclo inducido de longitud 4.
Los gráficos bipartitos cordales tienen varias caracterizaciones en términos de ordenamiento de eliminación perfecta , hipergráficos y matrices . Están estrechamente relacionados con los grafos fuertemente cordales . Por definición, los gráficos bipartitos cordales tienen una caracterización de subgrafo prohibido como los gráficos que no contienen ningún ciclo inducido de longitud 3 o de longitud al menos 5 (los llamados agujeros) como un subgrafo inducido . Por lo tanto, un gráfico G es bipartito cordal si y sólo si G no tiene triángulos ni agujeros. En Golumbic (1980), se mencionan otras dos caracterizaciones: B es bipartito cordal si y solo si cada separador de borde mínimo induce un subgrafo bipartito completo en B si y solo si cada subgrafo inducido es bipartito de eliminación perfecta.
Martin Farber ha demostrado: Un grafo es fuertemente cordal si y sólo si el gráfico de incidencia bipartito de su hipergrafo de camarilla es bipartito cordal. [2]
Una caracterización similar es válida para el hipergrafo de vecindad cerrada: un grafo es fuertemente cordal si y sólo si el gráfico de incidencia bipartito de su hipergrafo de vecindad cerrada es bipartito cordal. [3]
Otro resultado encontrado por Elias Dahlhaus es: Un gráfico bipartito B = ( X , Y , E ) es bipartito cordal si y sólo si el gráfico dividido resultante de hacer de X una camarilla es fuertemente cordal. [4]
Un gráfico bipartito B = ( X , Y , E ) es bipartito cordal si y solo si cada subgrafo inducido de B tiene un orden máximo de vecindario X y un orden máximo de vecindario Y. [5]
Varios resultados describen la relación entre gráficos bipartitos cordales y hipergráficos de vecindad totalmente equilibrados de gráficos bipartitos. [6]
En [7] se ofrece una caracterización de los gráficos bipartitos cordales en términos de gráficos de intersección relacionados con los hipergrafos.
Un gráfico bipartito es bipartito cordal si y sólo si su matriz de adyacencia está totalmente equilibrada si y sólo si la matriz de adyacencia está libre de gamma. [8]
Los gráficos bipartitos cordales se pueden reconocer en el tiempo O(min( n 2 , ( n + m ) log n )) para un gráfico con n vértices ym aristas. [9]
Varios problemas, como el ciclo hamiltoniano, [10] el árbol de Steiner [11] y la dominación eficiente [12], siguen siendo NP completos en gráficos bipartitos cordales.
Varios otros problemas que pueden resolverse eficientemente para gráficos bipartitos se pueden resolver de manera más eficiente para gráficos bipartitos cordales como se analiza en [13]
Todo grafo bipartito cordal es un grafo modular . Los gráficos bipartitos cordales incluyen los gráficos bipartitos completos y los gráficos bipartitos distancia-hereditarios . [14]