Acyclic colouring of 1-planar graphs

DOI10.1016/S0166-218X(00)00359-0zbMath0996.05053OpenAlexW2058139201MaRDI QIDQ5954081

Andre Raspaud, Eric Sopena, Oleg V. Borodin, Alexandr V. Kostochka

Publication date: 6 November 2002

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0166-218x(00)00359-0

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Coloring of graphs and hypergraphs (05C15)

Related Items (39)

Total coloring of 1-toroidal graphs with maximum degree at least 11 and no adjacent triangles ⋮ An improved upper bound on the linear 2-arboricity of 1-planar graphs ⋮ Acyclic coloring of graphs of maximum degree five: nine colors are enough ⋮ Coloring vertices and faces of locally planar graphs ⋮ On edge colorings of 1-toroidal graphs ⋮ An annotated bibliography on 1-planarity ⋮ A linear time algorithm for testing maximal 1-planarity of graphs with a rotation system ⋮ Acyclic coloring of graphs without bichromatic long path ⋮ Right Angle Crossing Graphs and 1-Planarity ⋮ 1-planar graphs are odd 13-colorable ⋮ A note on 1-planar graphs ⋮ All 2-planar graphs having the same spanning subgraph ⋮ An improved upper bound for the acyclic chromatic number of 1-planar graphs ⋮ Acyclic edge coloring of 1-planar graphs without 4-cycles ⋮ Hardness transitions and uniqueness of acyclic colouring ⋮ IC-planar graphs are odd-10-colorable ⋮ On edge colorings of \(1\)-planar graphs ⋮ Right angle crossing graphs and 1-planarity ⋮ Every toroidal graph is acyclically 8-choosable ⋮ On \((p,1)\)-total labelling of 1-planar graphs ⋮ Re-embedding a 1-plane graph for a straight-line drawing in linear time ⋮ On partitioning the edges of 1-plane graphs ⋮ Light subgraphs in the family of 1-planar graphs with high minimum degree ⋮ List edge and list total coloring of 1-planar graphs ⋮ Acyclic improper colouring of graphs with maximum degree 4 ⋮ Light edges in 3-connected 2-planar graphs with prescribed minimum degree ⋮ A polyhedral study of the acyclic coloring problem ⋮ Note on improper coloring of $1$-planar graphs ⋮ Acyclic edge coloring of triangle-free 1-planar graphs ⋮ Equitable partition of plane graphs with independent crossings into induced forests ⋮ Exploring the disjunctive rank of some facet-inducing inequalities of the acyclic coloring polytope ⋮ Planar graphs without 4-cycles are acyclically 6-choosable ⋮ Light structures in 1-planar graphs with an application to linear 2-arboricity ⋮ Acyclic coloring of IC-planar graphs ⋮ Algorithms for 1-Planar Graphs ⋮ IC-Planar Graphs Are 6-Choosable ⋮ Minimum feedback vertex set and acyclic coloring. ⋮ The linear 2-arboricity of 1-planar graphs without 3-cycles ⋮ On total colorings of 1-planar graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Note to the paper of Grünbaum on acyclic colorings
• On acyclic colorings of planar graphs
• Good and semi-strong colorings of oriented planar graphs
• The star arboricity of graphs
• On acyclic colorings of graphs on surfaces
• Ein Sechsfarbenproblem auf der Kugel
• Acyclic Colourings of Planar Graphs with Large Girth
• A new proof of the 6 color theorem
• Acyclic colorings of planar graphs
• 25 pretty graph colouring problems

This page was built for publication: Acyclic colouring of 1-planar graphs