Gráfico demasiado lleno

---

En teoría de grafos , un gráfico sobrellenado es un gráfico cuyo tamaño es mayor que el producto de su grado máximo y la mitad de su orden piso , es decir, donde es el tamaño de G , es el grado máximo de G y es el orden de G. El concepto de un subgráfico overfull , un gráfico overfull que es un subgrafo , sigue inmediatamente. Una definición alternativa y más estricta de un subgráfico S demasiado lleno de un gráfico G requiere .${\displaystyle |E|>\Delta (G)\lpiso |V|/2\rpiso}$${\ estilo de visualización | E |}$${\ estilo de visualización \ estilo de visualización \ Delta (G)}$${\ estilo de visualización | V |}$${\ estilo de visualización \ estilo de visualización \ Delta (G) = \ Delta (S)}$

En 1986, Amanda Chetwynd y Anthony Hilton propusieron la siguiente conjetura que ahora se conoce como la conjetura del exceso . ^[1]

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

Para grafos en los que , hay como máximo tres subgrafos overfull inducidos , y es posible encontrar un subgrafo overfull en tiempo polinomial . Cuando , hay como máximo un subgrafo overfull inducido, y es posible encontrarlo en tiempo lineal. ^[3]${\ estilo de visualización \ Delta \ geq {\ frac {n} {3}}}$${\ estilo de visualización \ Delta \ geq {\ frac {n} {2}}}$

---