Better coloring of 3-colorable graphs
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866916269328957440 |
|---|---|
| author | Kawarabayashi, Ken-ichi Thorup, Mikkel Yoneda, Hirotaka |
| author_facet | Kawarabayashi, Ken-ichi Thorup, Mikkel Yoneda, Hirotaka |
| contents | We consider the problem of coloring a 3-colorable graph in polynomial time using as few colors as possible. This is one of the most challenging problems in graph algorithms.
In this paper using Blum's notion of ``progress'', we develop a new combinatorial algorithm for the following: Given any 3-colorable graph with minimum degree $\ds>\sqrt n$, we can, in polynomial time, make progress towards a $k$-coloring for some $k=\sqrt{n/\ds}\cdot n^{o(1)}$.
We balance our main result with the best-known semi-definite(SDP) approach which we use for degrees below $n^{0.605073}$. As a result, we show that $\tO(n^{0.19747})$ colors suffice for coloring 3-colorable graphs. This improves on the previous best bound of $\tO(n^{0.19996})$ by Kawarabayashi and Thorup in 2017. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2406_00357 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Better coloring of 3-colorable graphs Kawarabayashi, Ken-ichi Thorup, Mikkel Yoneda, Hirotaka Data Structures and Algorithms Combinatorics G.2.2 We consider the problem of coloring a 3-colorable graph in polynomial time using as few colors as possible. This is one of the most challenging problems in graph algorithms. In this paper using Blum's notion of ``progress'', we develop a new combinatorial algorithm for the following: Given any 3-colorable graph with minimum degree $\ds>\sqrt n$, we can, in polynomial time, make progress towards a $k$-coloring for some $k=\sqrt{n/\ds}\cdot n^{o(1)}$. We balance our main result with the best-known semi-definite(SDP) approach which we use for degrees below $n^{0.605073}$. As a result, we show that $\tO(n^{0.19747})$ colors suffice for coloring 3-colorable graphs. This improves on the previous best bound of $\tO(n^{0.19996})$ by Kawarabayashi and Thorup in 2017. |
| title | Better coloring of 3-colorable graphs |
| topic | Data Structures and Algorithms Combinatorics G.2.2 |
| url | https://arxiv.org/abs/2406.00357 |