Factorización de gráficos

En teoría de grafos , un factor de un grafo G es un subgrafo generador , es decir, un subgrafo que tiene el mismo conjunto de vértices que G. Un k - factor de un grafo es un subgrafo generador regular k , y una k -factorización divide las aristas del grafo en k -factores disjuntos. Se dice que un grafo G es k -factorizable si admite una k -factorización. En particular, un 1-factor es una coincidencia perfecta , y una 1-factorización de un grafo k -regular es una coloración adecuada de las aristas con k colores. Un 2-factor es una colección de ciclos que abarca todos los vértices del grafo.

Si un grafo es 1-factorizable entonces tiene que ser un grafo regular . Sin embargo, no todos los grafos regulares son 1-factorizables. Un grafo k -regular es 1-factorizable si tiene índice cromático k ; algunos ejemplos de tales grafos incluyen:

• Cualquier grafo bipartito regular . ^[1] El teorema del matrimonio de Hall se puede utilizar para demostrar que un grafo bipartito k -regular contiene una correspondencia perfecta. Se puede entonces eliminar la correspondencia perfecta para obtener un grafo bipartito ( k  − 1)-regular y aplicar el mismo razonamiento repetidamente.
• Cualquier gráfico completo con un número par de nodos (ver más abajo). ^[2]

Sin embargo, también hay gráficos k -regulares que tienen índice cromático k  + 1, y estos gráficos no son 1-factorizables; ejemplos de dichos gráficos incluyen:

• Cualquier gráfico regular con un número impar de nodos.
• El gráfico de Petersen .

La factorización en 1 de un grafo completo corresponde a los emparejamientos en un torneo de todos contra todos . La factorización en 1 de grafos completos es un caso especial del teorema de Baranyai relativo a la factorización en 1 de hipergrafos completos .

Un método para construir una factorización 1 de un grafo completo en un número par de vértices implica colocar todos los vértices menos uno en un polígono regular , con el vértice restante en el centro. Con esta disposición de vértices, una forma de construir un factor 1 del grafo es elegir una arista e desde el centro hasta un único vértice del polígono junto con todas las aristas posibles que se encuentran en líneas perpendiculares a e . Los factores 1 que se pueden construir de esta manera forman una factorización 1 del grafo.

El número de factorizaciones 1 distintas de K ₂ , K ₄ , K ₆ , K ₈ , ... es 1, 1, 6, 6240, 1225566720, 252282619805368320, 98758655816833727741338583040, ... ( OEIS : A000438 ).

Sea G un grafo k -regular con 2 n nodos. Si k es suficientemente grande, se sabe que G tiene que ser 1-factorizable:

• Si k  = 2 n  − 1, entonces G es el gráfico completo K _{2 n} , y por lo tanto 1-factorizable (ver arriba).
• Si k  = 2 n  − 2, entonces G se puede construir eliminando una correspondencia perfecta de K _{2 n} . Nuevamente, G es 1-factorizable.
• Chetwynd y Hilton (1985) muestran que si k  ≥ 12 n /7, entonces G es 1-factorizable.

La conjetura de factorización 1 ^{[3] es una} conjetura de larga data que establece que k  ≈  n es suficiente. En términos precisos, la conjetura es:

• Si n es impar y k  ≥  n , entonces G es 1-factorizable. Si n es par y k  ≥  n  − 1 entonces G es 1-factorizable.

La conjetura de sobrellenado implica la conjetura de 1 factorización.

Un par perfecto de una factorización 1 es un par de factores 1 cuya unión induce un ciclo hamiltoniano .

Una factorización 1 perfecta (P1F) de un grafo es una factorización 1 que tiene la propiedad de que cada par de factores 1 es un par perfecto. Una factorización 1 perfecta no debe confundirse con una correspondencia perfecta (también llamada 1-factor).

En 1964, Anton Kotzig conjeturó que todo grafo completo K _{2 n} donde n ≥ 2 tiene una factorización 1 perfecta. Hasta ahora, se sabe que los siguientes grafos tienen una factorización 1 perfecta: ^[4]

• la familia infinita de grafos completos K _{2 p} donde p es un primo impar (por Anderson y también Nakamura, independientemente),
• la familia infinita de grafos completos K _{p +1} donde p es un primo impar,
• y resultados adicionales esporádicos, incluyendo K _{2 n} donde 2 n ∈ {16, 28, 36, 40, 50, 126, 170, 244, 344, 730, 1332, 1370, 1850, 2198, 3126, 6860, 12168, 16808, 29792}. Algunos resultados más nuevos se recogen aquí.

Si el grafo completo K _{n +1} tiene una 1-factorización perfecta, entonces el grafo bipartito completo K _{n , n} también tiene una 1-factorización perfecta. ^[5]

Si un grafo es 2-factorizable, entonces tiene que ser 2 k -regular para algún entero k . Julius Petersen demostró en 1891 que esta condición necesaria también es suficiente: cualquier grafo 2 k -regular es 2-factorizable . ^[6]

Si un grafo conexo es 2 k -regular y tiene un número par de aristas, también puede ser k -factorizado, eligiendo cada uno de los dos factores como un subconjunto alterno de las aristas de un recorrido de Euler . ^[7] Esto se aplica sólo a grafos conexos; los contraejemplos desconectados incluyen uniones disjuntas de ciclos impares, o de copias de K _{2 k  +1} .

El problema de Oberwolfach se refiere a la existencia de 2-factorizaciones de grafos completos en subgrafos isomorfos . Pregunta para qué subgrafos es posible esto. Esto se sabe cuando el subgrafo es conexo (en cuyo caso es un ciclo hamiltoniano y este caso especial es el problema de la descomposición hamiltoniana ), pero el caso general permanece abierto .