Problema informático difícil en una clase especial de gráficos bipartitos

Estoy interesado en las propiedades de una clase de gráficos bipartitos donde todos los nodos en X son 3-regulares, todos los nodos en Y son 2-regulares, y | X | = | 2 Y / 3 | . Primero, ¿es esta una clase de gráficos bien conocida? En segundo lugar,$G(X \cup Y, E)$$X$$Y$$|X|=|2Y/3|$

¿Hay algún ejemplo de problema computacional intratable restringido a esta clase de gráficos bipartitos?

Dado un gráfico 3-regular puede construir un gráfico bipartito G ' con las propiedades requeridas eligiendo X = V e Y = E y para cada borde e k = ( u i , u j ) ∈ E agregar bordes ( u i , e k ) , ( e k , u j$G = \{V,E\}$$G'$$X = V$$Y = E$$e_k = (u_i,u_j) \in E$$(u_i, e_k), (e_k, u_j)$. Así que creo que puede encontrar algunos problemas difíciles a partir de problemas difíciles en gráficos de 3 regulares.

Por ejemplo, ISOMORFISMO SUBGRÁFICO es NP-duro para su clase de gráficos.

$G$$G' = \{X \cup Y, E'\}$$H'$$2|V|$$G'$$H'$$G$

$I(G)$$G$

$G$$k$$G$$k$$G$$k$$G$

Es posible que el problema del ancho de banda para estos gráficos sea NP-completo, ya que es NP-completo para los árboles donde cada vértice tiene un grado máximo de tres. (Fuente: problema GT40 en Garey y Johnson para gráficos generales; para árboles de bajo grado, Garey, Graham, Johnson y Knuth, "Resultados de complejidad para la minimización del ancho de banda", SIAM J. Appl. Math. 34: 477-495; Citeseer . )

$G$$k$$I(G)$$k$$I(K_{1,3})$$I(K_{1,3})$$I(G)$