Equitable coloring of graphs beyond planarity
Fuente:
arXiv
Salvato in:
| Autore principale: | |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866910913061191680 |
|---|---|
| author | Liu, Weichan |
| author_facet | Liu, Weichan |
| contents | An equitable coloring of a graph is a proper coloring where the sizes of any two different color classes do not differ by more than one. A graph is IC-planar if it can be drawn in the plane so that no two crossed edges have a common endpoint, and is NIC-planar graphs if it can be embedded in the plane in such a way that no two pairs of crossed edges share two endpoints. Zhang proved that every IC-planar graph with maximum degree $Δ\geq 12$ and every NIC-planar graph with maximum degree $Δ\geq 13$ have equitable $Δ$-colorings. In this paper, we reduce the threshold from 12 to 10 for IC-planar graphs and from 13 to 11 for NIC-planar graphs. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2504_12647 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Equitable coloring of graphs beyond planarity Liu, Weichan Combinatorics An equitable coloring of a graph is a proper coloring where the sizes of any two different color classes do not differ by more than one. A graph is IC-planar if it can be drawn in the plane so that no two crossed edges have a common endpoint, and is NIC-planar graphs if it can be embedded in the plane in such a way that no two pairs of crossed edges share two endpoints. Zhang proved that every IC-planar graph with maximum degree $Δ\geq 12$ and every NIC-planar graph with maximum degree $Δ\geq 13$ have equitable $Δ$-colorings. In this paper, we reduce the threshold from 12 to 10 for IC-planar graphs and from 13 to 11 for NIC-planar graphs. |
| title | Equitable coloring of graphs beyond planarity |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2504.12647 |