On acyclic colorings of graphs on surfaces

DOI10.1007/BF02762708zbMath0857.05033OpenAlexW2061409357MaRDI QIDQ1916898

Noga Alon, Daniel P. Sanders, Bojan Mohar

Publication date: 6 March 1997

Published in: Israel Journal of Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf02762708

zbMATH Keywords

surfaceEuler characteristicprojective planeacyclic chromatic numberchromatic numberacyclic coloringsBorodin's conjecture

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Related Items (22)

Separation dimension of graphs and hypergraphs ⋮ Boxicity of graphs on surfaces ⋮ Acyclic colorings of products of trees ⋮ Coloring parameters for graphs on surfaces ⋮ Universal targets for homomorphisms of edge-colored graphs ⋮ Acyclic coloring of graphs without bichromatic long path ⋮ On low tree-depth decompositions ⋮ On b-acyclic chromatic number of a graph ⋮ Grad and classes with bounded expansion. I: Decompositions ⋮ Hardness transitions and uniqueness of acyclic colouring ⋮ Information-sharing in social networks ⋮ Degenerate and star colorings of graphs on surfaces ⋮ \(\mathcal Q\)-Ramsey classes of graphs ⋮ Adjacency posets of planar graphs ⋮ Acyclic colorings of locally planar graphs ⋮ Bounds on the generalised acyclic chromatic numbers of bounded degree graphs ⋮ Acyclic improper colouring of graphs with maximum degree 4 ⋮ Acyclic colouring of 1-planar graphs ⋮ Coloring graphs without bichromatic cycles or paths ⋮ On the acyclic chromatic number of Hamming graphs ⋮ Homomorphisms of edge-colored graphs and Coxeter groups ⋮ Acyclic \(k\)-strong coloring of maps on surfaces

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Note to the paper of Grünbaum on acyclic colorings
• Every planar graph has an acyclic 7-coloring
• On acyclic colorings of planar graphs
• Every planar graph has an acyclic 8-coloring
• Note on a paper of B. Grünbaum on acyclic colorings
• Acyclic coloring of graphs
• An acyclic analogue to Heawood's theorem
• SOLUTION OF THE HEAWOOD MAP-COLORING PROBLEM
• Acyclic colorings of planar graphs

This page was built for publication: On acyclic colorings of graphs on surfaces