Varios gráficos conocidos son de segundo grado, entre ellos:
El gráfico completo K 5 , un grafo cuártico con 5 vértices, el grafo cuártico más pequeño posible.
El grafo de Chvátal , otro grafo cuártico con 12 vértices, el grafo cuártico más pequeño que no tiene triángulos y no se puede colorear con tres colores. [2]
Todo grafo medial es un grafo de plano cuártico , y todo grafo de plano cuártico es el grafo medial de un par de grafos de plano dual o multigrafos. [5] Los diagramas de nudos y los diagramas de enlaces también son multigrafos de plano cuártico , en los que los vértices representan los cruces del diagrama y están marcados con información adicional sobre cuál de las dos ramas del nudo cruza la otra rama en ese punto. [6]
Propiedades
Como el grado de cada vértice en un grafo cuártico es par, cada grafo cuártico conectado tiene un recorrido de Euler . Y como con los grafos bipartitos regulares de manera más general, cada grafo cuártico bipartito tiene una correspondencia perfecta . En este caso, es posible un algoritmo mucho más simple y rápido para encontrar dicha correspondencia que para grafos irregulares: al seleccionar cada dos aristas de un recorrido de Euler, se puede encontrar un 2-factor , que en este caso debe ser una colección de ciclos, cada uno de longitud par, con cada vértice del grafo apareciendo en exactamente un ciclo. Al seleccionar cada dos aristas nuevamente en estos ciclos, se obtiene una correspondencia perfecta en tiempo lineal . El mismo método también se puede utilizar para colorear las aristas del grafo con cuatro colores en tiempo lineal. [7]
Es una conjetura abierta si todos los grafos hamiltonianos de segundo grado tienen un número par de circuitos hamiltonianos o si tienen más de un circuito hamiltoniano. Se sabe que la respuesta es falsa para los multigrafos de segundo grado . [9]
Véase también
Wikimedia Commons tiene medios relacionados con grafos 4-regulares .
^ Toida, S. (1974), "Construcción de grafos cuárticos", Journal of Combinatorial Theory , Serie B, 16 : 124–133, doi : 10.1016/0095-8956(74)90054-9 , MR 0347693.
^ Folkman, Jon (1967), "Gráficos regulares simétricos en línea", Journal of Combinatorial Theory , 3 : 215–232, doi : 10.1016/s0021-9800(67)80069-3 , MR 0224498.
^ Meredith, GHJ (1973), " Gráficos no hamiltonianos no coloreables en los bordes, n-valentes y n-conectados " , Journal of Combinatorial Theory , Serie B, 14 : 55–60, doi : 10.1016/s0095-8956(73)80006-1 , MR 0311503.
^ Bondy, JA; Häggkvist, R. (1981), "Ciclos de Hamilton con bordes disjuntos en gráficos planos regulares de 4", Aequationes Mathematicae , 22 (1): 42–45, doi :10.1007/BF02190157, MR 0623315.
^ Welsh, Dominic JA (1993), "La complejidad de los nudos", Quo vadis, teoría de grafos?, Annals of Discrete Mathematics, vol. 55, Ámsterdam: Holanda Septentrional, págs. 159-171, doi :10.1016/S0167-5060(08)70385-6, MR 1217989.
^ Gabow, Harold N. (1976), "Uso de particiones de Euler para colorear los bordes de multigrafos bipartitos", International Journal of Computer and Information Sciences , 5 (4): 345–355, doi :10.1007/bf00998632, MR 0422081.
^ Thomason, AG (1978), "Ciclos hamiltonianos y gráficos con aristas coloreables de forma única", Annals of Discrete Mathematics , 3 : 259–268, doi :10.1016/s0167-5060(08)70511-9, MR 0499124.
^ Fleischner, Herbert (1994), "Singularidad de los ciclos dominantes máximos en grafos 3-regulares y de los ciclos hamiltonianos en grafos 4-regulares", Journal of Graph Theory , 18 (5): 449–459, doi :10.1002/jgt.3190180503, MR 1283310.
