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 a una distancia > 1 entre sí en el ciclo. [1] Un nombre mejor sería débilmente cordal y bipartito ya que los grafos bipartitos cordales en general no son cordales como lo muestra el ciclo inducido de longitud 4.
Los grafos bipartitos cordales tienen varias caracterizaciones en términos de ordenamientos de eliminación perfecta , hipergrafos y matrices . Están estrechamente relacionados con los grafos fuertemente cordales . Por definición, los grafos bipartitos cordales tienen una caracterización de subgrafo prohibido como los grafos 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 grafo G es bipartito cordal si y solo si G está libre de triángulos y libre de agujeros. En Golumbic (1980), se mencionan otras dos caracterizaciones: B es bipartito cordal si y solo si cada separador de aristas 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 grafo de incidencia bipartito de su hipergrafo de camarilla es bipartito cordal. [2]
Una caracterización similar se aplica al hipergrafo de vecindad cerrada: un grafo es fuertemente cordal si y solo si el grafo de incidencia bipartito de su hipergrafo de vecindad cerrada es bipartito cordal. [3]
Otro resultado encontrado por Elias Dahlhaus es: Un grafo bipartito B = ( X , Y , E ) es bipartito cordal si y sólo si el grafo dividido que resulta de hacer de X una camarilla es fuertemente cordal. [4]
Un grafo bipartito B = ( X , Y , E ) es bipartito cordal si y solo si cada subgrafo inducido de B tiene un ordenamiento de vecindad X máximo y un ordenamiento de vecindad Y máximo. [5]
Varios resultados describen la relación entre los grafos bipartitos cordales y los hipergrafos de vecindad totalmente equilibrados de grafos bipartitos. [6]
En [7] se presenta una caracterización de los gráficos bipartitos cordales en términos de gráficos de intersección relacionados con hipergrafos.
Un grafo bipartito es bipartito cordal si y solo si su matriz de adyacencia está totalmente equilibrada si y solo si la matriz de adyacencia está libre de gamma. [8]
Los grafos bipartitos cordales se pueden reconocer en el tiempo O(min( n 2 , ( n + m ) log n )) para un grafo con n vértices y m 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 se pueden resolver de manera eficiente 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 grafos bipartitos cordales incluyen los grafos bipartitos completos y los grafos bipartitos hereditarios de distancia . [14]