stringtranslate.com

Gráfico de línea perfecta

Un gráfico lineal perfecto. Los bordes de cada componente biconectado se colorean de negro si el componente es bipartito, de azul si el componente es un tetraedro y de rojo si el componente es un libro de triángulos.

En teoría de grafos , una gráfica lineal perfecta es una gráfica cuya gráfica lineal es una gráfica perfecta . De manera equivalente, estas son las gráficas en las que cada ciclo simple de longitud impar es un triángulo. [1]

Una gráfica es recta perfecta si y sólo si cada uno de sus componentes biconectados es una gráfica bipartita , la gráfica completa K 4 , o un libro triangular K 1,1, n . [2] Debido a que estos tres tipos de componentes biconectados son todos gráficos perfectos en sí mismos, cada gráfico lineal perfecto es en sí mismo perfecto. [1] Por un razonamiento similar, cada gráfico lineal perfecto es un gráfico de paridad , [3] un gráfico de Meyniel , [4] y un gráfico perfectamente ordenable .

Los gráficos de líneas perfectas generalizan los gráficos bipartitos y comparten con ellos las propiedades de que la coincidencia máxima y la cobertura mínima de vértices tienen el mismo tamaño y que el índice cromático es igual al grado máximo . [5]

Ver también

Referencias

  1. ^ ab Trotter, LE Jr. (1977), "Gráficos lineales perfectos", Programación matemática , 12 (2): 255–259, doi :10.1007/BF01593791, MR  0457293
  2. ^ Maffray, Frédéric (1992), "Núcleos en gráficos de líneas perfectas", Journal of Combinatorial Theory , Serie B, 55 (1): 1–8, doi : 10.1016/0095-8956(92)90028-V , SEÑOR  1159851.
  3. ^ Grötschel, Martín ; Lovász, László ; Schrijver, Alexander (1993), Algoritmos geométricos y optimización combinatoria, Algoritmos y combinatoria, vol. 2 (2ª ed.), Springer-Verlag, Berlín, doi :10.1007/978-3-642-78240-4, ISBN 978-3-642-78242-8, señor  1261419
  4. ^ Wagler, Annegret (2001), "Aristas críticas y anticríticas en gráficos perfectos", Conceptos teóricos de grafos en informática: 27º taller internacional, WG 2001, Boltenhagen, Alemania, 14 al 16 de junio de 2001, Actas , Apuntes de conferencias en informática Ciencia, vol. 2204, Berlín: Springer, págs. 317–327, doi :10.1007/3-540-45477-2_29, MR  1905643.
  5. ^ de Werra, D. (1978), "Gráficos perfectos en línea", Programación matemática , 15 (2): 236–238, doi :10.1007/BF01609025, MR  0509968.