Difference of Facial Achromatic Numbers between Two Triangular Embeddings of a Graph

DOI10.20429/TAG.2023.10206MaRDI QIDQ6147457zbMATH OpenOpenAlexFDO

Authors Kengo Enami, Yumiko Ohno

Publication date 15 January 2024

Published in Theory and Applications of Graphs (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/2104.01553

zbMATH Keywords

facial 3-complete \(k\)-coloring of a triangulation

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Abstract: 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 $ps{i}_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^{\prime }$ on a surface, $ps{i}_3(G)$ may not be equal to $ps{i}_3(G^{\prime })$ even if $G$ is isomorphic to $G^{\prime }$ as graphs. Hence, it would be interesting to see how large the difference between $ps{i}_3(G)$ and $ps{i}_3(G^{\prime })$ can be. We shall show that the upper bound for such difference in terms of the genus of the surface.

Recommendations

• Facial achromatic number of triangulations on the sphere
• scientific article; zbMATH DE number 7491438
• Publication:4484788
• Achromatic number and facial achromatic number of connected locally-connected graphs
• Coloring face hypergraphs on surfaces

This page was built for publication: Difference of Facial Achromatic Numbers between Two Triangular Embeddings of a Graph

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6147457)