1 factorización del gráfico de Desargues : cada clase de color es un factor 1 .El gráfico de Petersen se puede dividir en 1 factor (rojo) y 2 factores (azul). Sin embargo, la gráfica no es unifactorable .
En teoría de grafos , un factor de un gráfico G es un subgrafo de expansión , es decir, un subgrafo que tiene el mismo vértice establecido que G. Un k -factor de un gráfico es un k - subgrafo regular que se extiende , y una k -factorización divide los bordes del gráfico en k -factores disjuntos. Se dice que un gráfico G es k -factorizable si admite una k -factorización. En particular, un factor 1 es una coincidencia perfecta , y una factorización 1 de un gráfico k -regular es una coloración de borde adecuada con k colores. Un factor de 2 es una colección de ciclos que abarca todos los vértices del gráfico.
1-factorización
Si una gráfica es 1 factorizable, entonces tiene que ser una gráfica regular . Sin embargo, no todas las gráficas regulares son factorizables en 1 factor. Un gráfico k -regular es factorizable en 1 si tiene un índice cromático k ; ejemplos de tales gráficos incluyen:
Cualquier gráfico bipartito regular . [1] El teorema del matrimonio de Hall se puede utilizar para demostrar que un gráfico bipartito k -regular contiene una coincidencia perfecta. Luego se puede eliminar la coincidencia perfecta para obtener un gráfico bipartito regular ( k − 1) 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 k -gráficos regulares que tienen índice cromático k + 1, y estos gráficos no son factorizables en 1; ejemplos de tales gráficos incluyen:
Cualquier gráfico regular con un número impar de nodos.
1 factorización de K 8 en la que cada 1 factor consta de una arista desde el centro hasta un vértice de un heptágono junto con todas las posibles aristas perpendiculares
Un método para construir una factorización 1 de un gráfico 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 gráfico es elegir una arista e desde el centro hasta un solo vértice de polígono junto con todas las aristas posibles que se encuentran en líneas perpendiculares a e . Los 1 factores que se pueden construir de esta manera forman una factorización 1 del gráfico.
El número de factorizaciones 1 distintas de K 2 , K 4 , K 6 , K 8 , ... es 1, 1, 6, 6240, 1225566720, 252282619805368320, 98758655816833727741338583040, ... ( OEIS : 8 ).
Conjetura de 1 factorización
Sea G un gráfico 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 tanto, 1 factorizable (ver arriba).
Si k = 2 n − 2, entonces G se puede construir eliminando una coincidencia 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.
Un par perfecto de una factorización 1 es un par de 1 factores cuya unión induce un ciclo hamiltoniano .
Una factorización 1 perfecta (P1F) de una gráfica 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 un emparejamiento perfecto (también llamado 1 factor).
En 1964, Anton Kotzig conjeturó que todo gráfico completo K 2 n donde n ≥ 2 tiene una factorización 1 perfecta. Hasta ahora, se sabe que las siguientes gráficas tienen una factorización perfecta en 1: [4]
la familia infinita de gráficos completos K 2 p donde p es un primo impar (por Anderson y también Nakamura, de forma independiente),
la familia infinita de gráficos completos K p +1 donde p es un primo impar,
y resultados adicionales esporádicos, incluido 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 recientes se recopilan aquí.
Si el gráfico completo K n +1 tiene una factorización 1 perfecta, entonces el gráfico bipartito completo K n , n también tiene una factorización 1 perfecta. [5]
Si un gráfico conectado es 2 k -regular y tiene un número par de aristas, también puede factorizarse k , 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 gráficos conectados; 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 gráficos completos en subgrafos isomórficos . Pregunta para qué subgrafos esto es posible. 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 .
^ Chetwynd y Hilton (1985). Niessen (1994). Perkovic y Reed (1997). Oeste.
^ Wallis, WD (1997), "16. Factorizaciones perfectas", Factorizaciones simples , Matemáticas y sus aplicaciones, vol. 390 (1 ed.), Springer EE. UU ., pág. 125, doi :10.1007/978-1-4757-2564-3_16, ISBN978-0-7923-4323-3
^ Bryant, Darryn; Maenhaut, Barbara M.; Wanless, Ian M. (mayo de 2002), "Una familia de factorizaciones perfectas de gráficos bipartitos completos", Journal of Combinatorial Theory , A, 98 (2): 328–342, doi : 10.1006/jcta.2001.3240 , ISSN 0097-3165
^ Petersen (1891), §9, pág. 200. Harary (1969), Teorema 9.9, pág. 90. Véase Diestel (2005), Corolario 2.1.5, p. 39 para una prueba.
^ Petersen (1891), §6, pág. 198.
Bibliografía
Bondy, John Adrián ; Murty, USR (1976), Teoría de grafos con aplicaciones, Holanda Septentrional, ISBN 0-444-19451-7, archivado desde el original el 13 de abril de 2010 , consultado el 18 de diciembre de 2019, Sección 5.1: "Coincidencias".
Chetwynd, AG ; Hilton, AJW (1985), "Las gráficas regulares de alto grado son factorizables en 1", Actas de la Sociedad Matemática de Londres , 50 (2): 193–206, doi :10.1112/plms/s3-50.2.193.
Diestel, Reinhard (2005), Teoría de grafos (3.ª ed.), Springer , ISBN 3-540-26182-6, Capítulo 2: "Combinación, revestimiento y embalaje". Edición electrónica.
Harary, Frank (1969), Teoría de grafos , Addison-Wesley, ISBN 0-201-02787-9, Capítulo 9: "Factorización".
Niessen, Thomas (1994), "Cómo encontrar subgrafos demasiado llenos en gráficos con un grado máximo grande", Matemáticas Aplicadas Discretas , 51 (1–2): 117–125, doi :10.1016/0166-218X(94)90101-5.
Perkovic, L.; Reed, B. (1997), "Gráficos regulares de alto grado para colorear bordes", Matemáticas discretas , 165–166: 567–578, doi :10.1016/S0012-365X(96)00202-6.
Plummer, Michael D. (2007), "Factores gráficos y factorización: 1985-2003: una encuesta", Matemáticas discretas , 307 (7–8): 791–821, doi :10.1016/j.disc.2005.11.059.
