Odd coloring of 2-boundary planar graphs and beyond
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2022
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866913775663185920 |
|---|---|
| author | Liu, Weichan Qi, Mengke Zhang, Xin |
| author_facet | Liu, Weichan Qi, Mengke Zhang, Xin |
| contents | In this paper, we introduce the notion of 2-boundary planar graphs. A graph is 2-boundary planar if it has an embedding in the plane so that all vertices lie on the boundary of at most two faces and no edges are crossed. A proper coloring of a graph is odd if every non-isolated vertex has some color that appears an odd number of times on its neighborhood. Petruševski and Škrekovski conjectured in 2022 that every planar graph admits an odd 5-coloring. We confirm this conjecture for 2-boundary planar graphs. Moreover, we present several questions regarding 2-boundary planar graphs that are of independent interest. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2205_09317 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | Odd coloring of 2-boundary planar graphs and beyond Liu, Weichan Qi, Mengke Zhang, Xin Combinatorics Discrete Mathematics 05C15, 05C10 In this paper, we introduce the notion of 2-boundary planar graphs. A graph is 2-boundary planar if it has an embedding in the plane so that all vertices lie on the boundary of at most two faces and no edges are crossed. A proper coloring of a graph is odd if every non-isolated vertex has some color that appears an odd number of times on its neighborhood. Petruševski and Škrekovski conjectured in 2022 that every planar graph admits an odd 5-coloring. We confirm this conjecture for 2-boundary planar graphs. Moreover, we present several questions regarding 2-boundary planar graphs that are of independent interest. |
| title | Odd coloring of 2-boundary planar graphs and beyond |
| topic | Combinatorics Discrete Mathematics 05C15, 05C10 |
| url | https://arxiv.org/abs/2205.09317 |