Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2021
|
| Soggetti: | |
| Accesso online: | https://arxiv.org/abs/2104.01553 |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866910317933494272 |
|---|---|
| author | Enami, Kengo Ohno, Yumiko |
| author_facet | Enami, Kengo Ohno, Yumiko |
| contents | A facial $3$-complete $k$-coloring of a triangulation $G$ on a surface is a vertex $k$-coloring such that every triple of $k$-colors appears on the boundary of some face of $G$. The facial $3$-achromatic number $ψ_3(G)$ of $G$ is the maximum integer $k$ such that $G$ has a facial $3$-complete $k$-coloring. This notion is an expansion of the complete coloring, that is, a proper vertex coloring of a graph such that every pair of colors appears on the ends of some edge.
For two triangulations $G$ and $G'$ on a surface, $ψ_3(G)$ may not be equal to $ψ_3(G')$ even if $G$ is isomorphic to $G'$ as graphs. Hence, it would be interesting to see how large the difference between $ψ_3(G)$ and $ψ_3(G')$ can be. We shall show that the upper bound for such difference in terms of the genus of the surface. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2104_01553 |
| institution | arXiv |
| publishDate | 2021 |
| record_format | arxiv |
| spellingShingle | Difference of facial achromatic numbers between two triangular embeddings of a graph Enami, Kengo Ohno, Yumiko Combinatorics 05C10, 05C12 A facial $3$-complete $k$-coloring of a triangulation $G$ on a surface is a vertex $k$-coloring such that every triple of $k$-colors appears on the boundary of some face of $G$. The facial $3$-achromatic number $ψ_3(G)$ of $G$ is the maximum integer $k$ such that $G$ has a facial $3$-complete $k$-coloring. This notion is an expansion of the complete coloring, that is, a proper vertex coloring of a graph such that every pair of colors appears on the ends of some edge. For two triangulations $G$ and $G'$ on a surface, $ψ_3(G)$ may not be equal to $ψ_3(G')$ even if $G$ is isomorphic to $G'$ as graphs. Hence, it would be interesting to see how large the difference between $ψ_3(G)$ and $ψ_3(G')$ can be. We shall show that the upper bound for such difference in terms of the genus of the surface. |
| title | Difference of facial achromatic numbers between two triangular embeddings of a graph |
| topic | Combinatorics 05C10, 05C12 |
| url | https://arxiv.org/abs/2104.01553 |