Gráfico de desbordamiento

Problema sin resolver en matemáticas

Conjetura: Un grafo G con${\displaystyle \Delta (G)>n/3}$es de clase 2 si y solo si tiene un subgrafo sobrellenado S tal que${\displaystyle \displaystyle \Delta (G)=\Delta (S)}$.

Más problemas sin resolver en matemáticas

En teoría de grafos , un grafo sobrellenado es un grafo cuyo tamaño es mayor que el producto de su grado máximo y la mitad de su orden , es decir ,${\displaystyle |E|>\Delta (G)\lfloor |V|/2\rfloor }$dónde${\displaystyle |E|}$es el tamaño de G ,${\displaystyle \displaystyle \Delta (G)}$es el grado máximo de G y${\displaystyle |V|}$es el orden de G. El concepto de subgrafo sobrellenado , un grafo sobrellenado que es un subgrafo , se deriva inmediatamente. Una definición alternativa y más estricta de un subgrafo sobrellenado S de un grafo G requiere${\displaystyle \displaystyle \Delta (G)=\Delta (S)}$.

Todo grafo de ciclo impar de longitud tres o más está sobrellenado. El producto de su grado (dos) y la mitad de su longitud (redondeada hacia abajo) es uno menos que el número de aristas en el ciclo. De manera más general, todo grafo regular con un número impar de aristas está sobrellenado.${\displaystyle n}$de vértices está sobrecargado, debido a su número de aristas,${\displaystyle \Delta n/2}$(dónde${\displaystyle \Delta }$es su grado), es mayor que${\displaystyle \Delta \lfloor n/2\rfloor }$.

Algunas propiedades de los grafos sobrecargados:

1. Los gráficos sobrecargados son de orden impar.
2. Los grafos sobrecargados son de clase 2. Es decir, requieren al menos Δ + 1 colores en cualquier coloración de aristas .
3. Un grafo G , con un subgrafo sobrellenado S tal que${\displaystyle \displaystyle \Delta (G)=\Delta (S)}$, es de clase 2.

En 1986, Amanda Chetwynd y Anthony Hilton plantearon la siguiente conjetura que ahora se conoce como la conjetura de sobrecarga . ^{[ 1 ]}

Un gráfico G con${\displaystyle \Delta (G)>n/3}$es de clase 2 si y solo si tiene un subgrafo sobrellenado S tal que${\displaystyle \displaystyle \Delta (G)=\Delta (S)}$.

Esta conjetura, de ser cierta, tendría numerosas implicaciones en la teoría de grafos, incluida la conjetura de 1-factorización . ^{[ 2 ]}

Para gráficos en los que${\displaystyle \Delta \geq n/3}$, hay como máximo tres subgrafos sobrellenados inducidos , y es posible encontrar un subgrafo sobrellenado en tiempo polinomial . Cuando${\displaystyle \Delta \geq n/2}$, hay como máximo un subgrafo sobrellenado inducido, y es posible encontrarlo en tiempo lineal . ^{[ 3 ]}