Difference of facial achromatic numbers between two triangular embeddings of a graph

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 \(\psi_3(G)\) of \(G\) is the maximum integer \(k\) such that \(G\) has a f...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2021-04
Main Authors: Enami, Kengo, Ohno, Yumiko
Format: Article
Language:English
Subjects:
Graph coloring
Triangulation
Upper bounds
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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 \(\psi_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, \(\psi_3(G)\) may not be equal to \(\psi_3(G')\) even if \(G\) is isomorphic to \(G'\) as graphs. Hence, it would be interesting to see how large the difference between \(\psi_3(G)\) and \(\psi_3(G')\) can be. We shall show that the upper bound for such difference in terms of the genus of the surface.
ISSN:2331-8422
DOI:10.48550/arxiv.2104.01553