En teoría de grafos , particularmente en la teoría de hipergrafías , la gráfica lineal de una hipergrafía H , denotada como L( H ), es la gráfica cuyo conjunto de vértices es el conjunto de las hiperaristas de H , con dos vértices adyacentes en L( H ) cuando sus correspondientes hiperbordes tienen una intersección no vacía en H . En otras palabras, L( H ) es el gráfico de intersección de una familia de conjuntos finitos. Es una generalización del gráfico lineal de un gráfico.
Las preguntas sobre gráficos lineales de hipergrafías suelen ser generalizaciones de preguntas sobre gráficos lineales de gráficos. Por ejemplo, una hipergrafía cuyos bordes tienen todos tamaño k se llama k -uniforme . (Una hipergrafía de 2 uniformes es una gráfica). En la teoría de hipergrafías, a menudo es natural exigir que las hipergrafías sean k - uniformes. Cada gráfico es el gráfico lineal de algún hipergráfico, pero, dado un tamaño de borde fijo k , no todo gráfico es un gráfico lineal de algún hipergráfico k uniforme. Un problema principal es caracterizar aquellos que lo son, para cada k ≥ 3.
Una hipergrafía es lineal si cada par de hiperaristas se cruzan en un vértice como máximo. Cada gráfico es el gráfico lineal, no sólo de alguna hipergrafía, sino de alguna hipergrafía lineal ( Berge 1989 ).
Beineke (1968) caracterizó los gráficos lineales de gráficos mediante una lista de 9 subgrafos inducidos prohibidos . (Consulte el artículo sobre gráficos de líneas ). No se conoce ninguna caracterización por subgrafos inducidos prohibidos de los gráficos de líneas de k-hipergrafías uniformes para cualquier k ≥ 3, y Lovász (1977) demostró que no existe tal caracterización por una lista finita si k = 3 .
Krausz (1943) caracterizó los gráficos de líneas de gráficos en términos de coberturas de camarilla . (Consulte Gráficos lineales ). Berge (1989) proporcionó una caracterización global del tipo Krausz para los gráficos lineales de hipergrafías k -uniformes para cualquier k ≥ 3 .
Naik et al. proporcionaron una caracterización global del tipo Krausz para los gráficos lineales de k - hipergrafías lineales uniformes para cualquier k ≥ 3 . (1980) . Al mismo tiempo, encontraron una lista finita de subgrafos inducidos prohibidos para hipergrafos lineales de 3 uniformes con un grado mínimo de vértice de al menos 69. Metelsky & Tyshkevich (1997) y Jacobson, Kézdy & Lehel (1997) mejoraron este límite a 19. En último Skums, Suzdal' & Tyshkevich (2005) redujeron este límite a 16. Metelsky & Tyshkevich (1997) también probaron que, si k > 3, no existe tal lista finita para k lineal- hipergrafías uniformes, sin importar qué límite inferior se coloque en el grado.