On the \(d\)-distance face chromatic number of plane graphs
type: Item
instance of: scholarly article
title: On the \(d\)-distance face chromatic number of plane graphs
zbMATH Open document ID: 0880.05040
DOI: 10.1016/S0012-365X(96)00049-0
author: Mirko Horňák
author: Stanislav Jendroľ
published in: Discrete Mathematics
publication date: 1998-01-19T00:00:00Z
review text: Let \(G\) be a finite connected plane graph, and let \(F(G)\) be the set of all faces of \(G\). The distance of two faces \(f_1\), \(f_2\) of \(G\) is the minimum value of \(d(x_1,x_2)\) for \(x_i\in f_i\). For an integer \(d\leq 0\), the \(d\)-distance face \(k\)-colouring of \(G\) is a map \(\varphi: F(G)\to\{1,\dots, k\}\) such that if \(f_1\neq f_2\) and \(d(f_1,f_2)\leq d\) then \(\varphi(f_1)\neq\varphi(f_2)\). The minimum \(k\) for which such a map exists is called the \(d\)-distance face chromatic number, and is denoted by \(df_c(G)\). In this paper, an upper bound for \(df_c(G)\) is given when the maximum degree is greater than or equal to 8. Some known results for \(d=0\) are obtained as corollaries.
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 05C12
Mathematics Subject Classification ID: 05C10
zbMATH DE Number: 1019060
zbMATH Keywords: cyclic chromatic number
zbMATH Keywords: plane graph
zbMATH Keywords: distance
zbMATH Keywords: face chromatic number
reviewed by: Raffaele Scapellato
MaRDI profile type: Publication
cites work: Q3679212
cites work: Diagonal 11-coloring of plane triangulations
cites work: Q3987221
cites work: Cyclic coloring of plane graphs
cites work: Q3781771
cites work: Q3757929
cites work: On some properties of 4‐regular plane graphs
cites work: Q5591378
cites work: Cyclic coloration of 3-polytopes
cites work: Q4857375
cites work: On Diagonally 10‐Coloring Plane Triangulations
cites work: Ein Sechsfarbenproblem auf der Kugel
Recommended article: Q4329138
Recommended article: On the vertex face total chromatic number of planar graphs
Recommended article: Q4019911
Recommended article: Q4005786
Recommended article: Edge‐face chromatic number and edge chromatic number of simple plane graphs
Recommended article: Q4267311
Recommended article: On the chromatic numbers of some distance graphs
Recommended article: Q4278795
Recommended article: Q5455834
Recommended article: The chromatic numbers of distance graphs
description: scientific article; zbMATH DE number 1019060