Acyclic \(k\)-strong coloring of maps on surfaces
type: Item
instance of: scholarly article
title: Acyclic \(k\)-strong coloring of maps on surfaces
zbMATH Open document ID: 0965.05043
DOI: 10.1007/BF02675788
published in: Mathematical Notes
publication date: 2000-10-16T00:00:00Z
review text: A proper vertex-coloring of a graph is said to be acyclic if there are no two-colored cycles. The authors show that, if each face having size at most \(k\) (where \(k\geq 4\)) of a graph imbedding on a surface of characteristic \(N\) is replaced by a clique on the same vertex set, then the resulting pseudograph has an acyclic vertex-coloring of cardinality depending linearly on \(N\) and \(k\). Previously, such results were known only for \(N= 1\) or \(2\), and \(k= 3\) or \(4\).
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 05C10
zbMATH DE Number: 1517717
zbMATH Keywords: maps
zbMATH Keywords: vertex-coloring
zbMATH Keywords: face
zbMATH Keywords: surface
zbMATH Keywords: clique
zbMATH Keywords: pseudograph
author: Oleg V. Borodin
author: Alexandr Kostochka
author: André Raspaud
author: Éric Sopena
reviewed by: Arthur T. White
MaRDI profile type: Publication
cites work: Q4128618
cites work: Q3679212
cites work: Ein Sechsfarbenproblem auf der Kugel
cites work: Ein 7-Farbensatz 1-einbettbarer Graphen auf der projektiven Ebene
cites work: Q5591378
cites work: On cyclic colorings and their generalizations
cites work: Every planar graph has an acyclic 7-coloring
cites work: On acyclic colorings of graphs on surfaces
cites work: Homomorphisms of edge-colored graphs and Coxeter groups
cites work: Acyclic colorings of planar graphs
cites work: Good and semi-strong colorings of oriented planar graphs
cites work: The star arboricity of graphs
cites work: Q4936748
full work available at URL: https://doi.org/10.1007/bf02675788
OpenAlex ID: W1998236685
Recommended article: Estimating the minimal number of colors in acyclic \(k\)-strong colorings of maps on surfaces
Recommended article: On acyclic colorings of graphs on surfaces
Recommended article: On the Total Coloring of Graphs Embeddable in Surfaces
Recommended article: k-Chromatic Number of Graphs on Surfaces
Recommended article: Strong k-colourings of graphs
Recommended article: Coloring vertices and faces of maps on surfaces
Recommended article: Q3825062
Recommended article: The number of \(k\)-colorings of a graph on a fixed surface
Recommended article: Acyclic colorings of planar graphs
Recommended article: Q3832588
description: scientific article; zbMATH DE number 1517717