Embeddings of a Graph into a Surface with Different Weak Chromatic Numbers
- PDF / 355,545 Bytes
- 10 Pages / 439.37 x 666.142 pts Page_size
- 23 Downloads / 191 Views
(0123456789().,-volV)(0123456789().,-volV)
ORIGINAL PAPER
Embeddings of a Graph into a Surface with Different Weak Chromatic Numbers Kengo Enami1
•
Kenta Noguchi2
Received: 22 June 2020 / Revised: 15 October 2020 / Accepted: 24 October 2020 Ó Springer Japan KK, part of Springer Nature 2020
Abstract A weak coloring of a graph G embedded on a surface is a vertex coloring of G such that no face is monochromatic. The weak chromatic number of G is the minimum number k such that G has a weak k-coloring. Ku¨ndgen and Ramamurthi (J Combin Theory Ser B 85, 307–337, 2002) conjectured that for each positive integer k, there is a graph that has two different embeddings on the same surface whose weak chromatic numbers differ by at least k. In this paper, we answer this conjecture affirmatively in two ways. Keywords Weak coloring Facially-constrained coloring Triangulation Re-embedding
1 Introduction In this paper, we consider finite undirected graphs without loops, which may have multiple edges. A graph is called simple if it has no multiple edges. An embedding of a graph G on a surface F, which is a compact connected 2-dimensional manifold without boundary, is a drawing of G on F without edge crossing. By the classification theorem of surfaces, any surface is homeomorphic to either an orientable surface of genus g 0, denoted by Sg , or a non-orientable surface of genus k 1, denoted by Nk . The Euler genus of Sg is 2g and that of Nk is k. & Kengo Enami [email protected] Kenta Noguchi [email protected] 1
Graduate School of Environment and Information Sciences, Yokohama National University, 79-7 Tokiwadai, Hodogaya-ku, Yokohama 240-8501, Japan
2
Department of Information Sciences, Tokyo University of Science, 2641 Yamazaki, Noda, Chiba 278-8510, Japan
123
Graphs and Combinatorics
We often consider that a graph G is already embedded on a surface. If G has another embedding on some surface, then we denote it by f(G) to distinguish it from G. (Now we mean that f is an injective continuous map from the graph G to the surface.) The faces of a graph G embedded on a surface F are the connected components of the open set F G. We denote by V(F) the set of vertices in the boundary of a face F, and denote by F ðGÞ the set of faces of G. Throughout this paper, we assume that every embedding is cellular, that is, each face must be homeomorphic to an open 2-cell, and has no digons, that is, faces bounded by 2-cycles. A cycle (or closed walk) C of G is facial if C bounds a face of G. For terminology of topological graph theory, we refer to [5, 7] A (vertex) k-coloring of a graph G is a map c : VðGÞ ! f1; 2; . . .; kg. In this paper, a k-coloring c of G is not necessarily proper, that is, cðuÞ 6¼ cðvÞ for any two adjacent vertices u and v of G. Colorings of graphs embedded on surfaces with facial constraints have attracted a lot of attention. In particular, facially-constrained colorings of plane graphs, that is, graphs embedded on the sphere (or the plane), were overviewed by Czap and Jendrol’ [3]. Many facially-
Data Loading...
