stringtranslate.com

Gráfica de línea perfecta

Un gráfico lineal perfecto. Las aristas 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 , un grafo perfecto lineal es un grafo cuyo grafo lineal es un grafo perfecto . De manera equivalente, estos son los grafos en los que cada ciclo simple de longitud impar es un triángulo. [1]

Un grafo es perfecto lineal si y solo si cada uno de sus componentes biconexos es un grafo bipartito , el grafo completo K 4 o un libro triangular K 1,1, n . [2] Debido a que estos tres tipos de componentes biconexos son todos grafos perfectos en sí mismos, cada grafo perfecto lineal es en sí mismo perfecto. [1] Por un razonamiento similar, cada grafo perfecto lineal es un grafo de paridad , [3] un grafo de Meyniel , [4] y un grafo perfectamente ordenable .

Los gráficos lineales perfectos 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]

Véase también

Referencias

  1. ^ ab Trotter, LE Jr. (1977), "Gráficos de línea perfecta", Programación matemática , 12 (2): 255–259, doi :10.1007/BF01593791, MR  0457293
  2. ^ Maffray, Frédéric (1992), "Núcleos en grafos lineales perfectos", Journal of Combinatorial Theory , Serie B, 55 (1): 1–8, doi : 10.1016/0095-8956(92)90028-V , MR  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, Sr.  1261419
  4. ^ Wagler, Annegret (2001), "Aristas críticas y anticríticas en grafos perfectos", Graph-Theoretic Concepts in Computer Science: 27th International Workshop, WG 2001, Boltenhagen, Alemania, 14-16 de junio de 2001, Actas , Lecture Notes in Computer Science, vol. 2204, Berlín: Springer, pp. 317-327, doi :10.1007/3-540-45477-2_29, MR  1905643.
  5. ^ de Werra, D. (1978), "Gráficos lineales perfectos", Programación matemática , 15 (2): 236–238, doi :10.1007/BF01609025, MR  0509968.