Gráfico de bordes perfectos

Un gráfico de aristas perfectas es un gráfico cuyo gráfico lineal es perfecto . De manera equivalente, estos son gráficos donde cada ciclo simple de longitud impar es un triángulo [1] .

Un gráfico es de aristas perfectas si y solo si cualquiera de sus componentes doblemente conectados es un gráfico bipartito , un gráfico completo o un libro de triángulos [2] . Dado que estos tres tipos de componentes doblemente conectados son en sí mismos gráficos perfectos, cualquier gráfico con aristas perfectas es en sí mismo perfecto [1] . Por razones similares, cualquier gráfico de bordes perfectos es un gráfico de paridad [3] , un gráfico de Meinel [4] y un gráfico bien ordenado .

Los grafos de bordes perfectos generalizan los grafos bipartitos y comparten con ellos las propiedades de que la coincidencia más grande y la cubierta de vértice más pequeña tienen el mismo tamaño, y el índice cromático es igual al grado máximo [5] .

Véase también

Notas

  1. ↑ 12 Trotter LE, Jr. Gráficos de líneas perfectas // Programación Matemática . - 1977. - T. 12 , núm. 2 . — S. 255–259 . -doi : 10.1007/ BF01593791 .
  2. ↑ Frédéric Maffray. Núcleos en gráficos de líneas perfectos // Journal of Combinatorial Theory . - 1992. - T. 55 , núm. 1 . — P. 1–8 . -doi : 10.1016 / 0095-8956(92)90028-V . .
  3. ↑ Martin Grötschel, László Lovász, Alexander Schrijver. Algoritmos geométricos y optimización combinatoria . — 2do. - Springer-Verlag, Berlín, 1993. - V. 2. - S. 281. - (Algoritmos y Combinatoria). — ISBN 3-540-56740-2 . -doi : 10.1007 / 978-3-642-78240-4 . .
  4. ↑ Annegret Wagler. Bordes críticos y anticríticos 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. - Springer, 2001. - T. 2204. - S. 317-327. — (Apuntes de clase en informática). -doi : 10.1007/ 3-540-45477-2_29 . .
  5. ↑ Gráficos en línea perfecta // Programación matemática . - 1978. - T. 15 . - Pág. 236-238. -doi : 10.1007/ BF01609025 . .