Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2412.01374 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909670936936448 |
|---|---|
| author | Abe, Yayoi Setoh, Auna Yoneda, Gen |
| author_facet | Abe, Yayoi Setoh, Auna Yoneda, Gen |
| contents | The vertex coloring problem to find chromatic numbers is known to be unsolvable in polynomial time. Although various algorithms have been proposed to efficiently compute chromatic numbers, they tend to take an enormous amount of time for large graphs. In this paper, we propose a recurrence relation to rapidly obtain the expected value of the chromatic number of random graphs. Then we compare the results obtained using this recurrence relation with other methods using an exact investigation of all graphs, the Monte Carlo method, the iterated random color matching method, and the method presented in Bollobás' previous studies. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2412_01374 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Chromatic number of random graphs: an approach using a recurrence relation Abe, Yayoi Setoh, Auna Yoneda, Gen Combinatorics The vertex coloring problem to find chromatic numbers is known to be unsolvable in polynomial time. Although various algorithms have been proposed to efficiently compute chromatic numbers, they tend to take an enormous amount of time for large graphs. In this paper, we propose a recurrence relation to rapidly obtain the expected value of the chromatic number of random graphs. Then we compare the results obtained using this recurrence relation with other methods using an exact investigation of all graphs, the Monte Carlo method, the iterated random color matching method, and the method presented in Bollobás' previous studies. |
| title | Chromatic number of random graphs: an approach using a recurrence relation |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2412.01374 |