Max-camarilla en gráfico lineal de hipergrafía

Supongamos que tenemos un multigraph (más tarde, un multihipegraph). Una camarilla de borde es un conjunto de bordes que se cruzan por pares (tienen al menos un vértice común). Entonces, cualquier camarilla de borde en un multigrafo siempre cae en una de dos categorías:$C$

• Una estrella : hay un vértice tal que cada borde de contiene$C$
• Un triángulo : hay tres vértices de tal manera que cada borde de va entre dos de ellos.$C$

Esto lleva a un algoritmo fácil de tiempo para calcular la camarilla de borde más grande.$O(n^3)$

Estoy bastante seguro de que uno puede mostrar de manera más general, que por cada , en múltiples hiperígrafos con un tamaño máximo de borde r , puede probar un cierto teorema de estructura para las camarillas de hiperedge, y obtener un algoritmo de tiempo polinómico para encontrar la camarilla máxima.$r$$r$

¿Hay algo relacionado con este resultado conocido? Además, el algoritmo que tengo en mente es un polinomio de grado extremadamente alto; Sería bueno obtener algo con tiempo de ejecución o mejor.$n^{\mathrm{poly}(r)}$

Esto me pareció interesante ya que la camarilla de borde máxima es un límite inferior en el número cromático de borde (también conocido como índice cromático).

$2^{2^{\mathrm{exp}(r)}}n^{\mathrm{exp}(r)}$

Cada gráfico G es un gráfico lineal de alguna hipergrafía, por ejemplo, la que tiene los bordes de G como sus vértices y los conjuntos de bordes adyacentes a cada vértice de G como sus hipereduras. Por lo tanto, encontrar camarillas en gráficos de líneas de hipergrafías no puede ser más fácil que encontrar camarillas en gráficos arbitrarios.

$r$$G$$r$$n^{poly(r)}$