Towards the Overfull Conjecture
Fuente:
arXiv
Guardado en:
| Autor principal: | |
|---|---|
| Formato: | Preprint |
| Publicado: |
2023
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866912016600399872 |
|---|---|
| author | Shan, Songling |
| author_facet | Shan, Songling |
| contents | Let $G$ be a simple graph with maximum degree denoted as $Δ(G)$. An overfull subgraph $H$ of $G$ is a subgraph satisfying the condition $|E(H)| > Δ(G)\lfloor \frac{1}{2}|V(H)| \rfloor$. In 1986, Chetwynd and Hilton proposed the Overfull Conjecture, stating that a graph $G$ with maximum degree $Δ(G)> \frac{1}{3}|V(G)|$ has chromatic index equal to $Δ(G)$ if and only if it does not contain any overfull subgraph. The Overfull Conjecture has many implications. For example, it implies a polynomial-time algorithm for determining the chromatic index of graphs $G$ with $Δ(G) > \frac{1}{3}|V(G)|$, and implies several longstanding conjectures in the area of graph edge colorings. In this paper, we make the first breakthrough towards the conjecture when not imposing a minimum degree condition on the graph: for any $0<\varepsilon \le \frac{1}{14}$, there exists a positive integer $n_0$ such that if $G$ is a graph on $n\ge n_0$ vertices with $Δ(G) \ge (1-\varepsilon)n$, then the Overfull Conjecture holds for $G$. The previous best result in this direction, due to Chetwynd and Hilton from 1989, asserts the conjecture for graphs $G$ with $Δ(G) \ge |V(G)|-3$. Our result also implies the Average Degree Conjecture of Vizing from 1968 for the same class of graphs $G$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2308_16808 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Towards the Overfull Conjecture Shan, Songling Combinatorics Let $G$ be a simple graph with maximum degree denoted as $Δ(G)$. An overfull subgraph $H$ of $G$ is a subgraph satisfying the condition $|E(H)| > Δ(G)\lfloor \frac{1}{2}|V(H)| \rfloor$. In 1986, Chetwynd and Hilton proposed the Overfull Conjecture, stating that a graph $G$ with maximum degree $Δ(G)> \frac{1}{3}|V(G)|$ has chromatic index equal to $Δ(G)$ if and only if it does not contain any overfull subgraph. The Overfull Conjecture has many implications. For example, it implies a polynomial-time algorithm for determining the chromatic index of graphs $G$ with $Δ(G) > \frac{1}{3}|V(G)|$, and implies several longstanding conjectures in the area of graph edge colorings. In this paper, we make the first breakthrough towards the conjecture when not imposing a minimum degree condition on the graph: for any $0<\varepsilon \le \frac{1}{14}$, there exists a positive integer $n_0$ such that if $G$ is a graph on $n\ge n_0$ vertices with $Δ(G) \ge (1-\varepsilon)n$, then the Overfull Conjecture holds for $G$. The previous best result in this direction, due to Chetwynd and Hilton from 1989, asserts the conjecture for graphs $G$ with $Δ(G) \ge |V(G)|-3$. Our result also implies the Average Degree Conjecture of Vizing from 1968 for the same class of graphs $G$. |
| title | Towards the Overfull Conjecture |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2308.16808 |