A linear-time algorithm for 7-coloring 1-plane graphs

DOI10.1007/s00453-004-1134-xzbMath1082.05084OpenAlexW1986153011MaRDI QIDQ818664

Zhi-Zhong Chen, Mitsuharu Kouno

Publication date: 21 March 2006

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-004-1134-x

zbMATH Keywords

NP-completecoloring

Mathematics Subject Classification ID

Nonnumerical algorithms (68W05) Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (14)

On edge colorings of 1-toroidal graphs ⋮ \(K_7\)-minors in optimal 1-planar graphs ⋮ An annotated bibliography on 1-planarity ⋮ Proper 1-immersions of graphs triangulating the plane ⋮ On drawings and decompositions of 1-planar graphs ⋮ All 2-planar graphs having the same spanning subgraph ⋮ 1-planarity of complete multipartite graphs ⋮ A note on odd colorings of 1-planar graphs ⋮ Minimal non-1-planar graphs ⋮ The matching extendability of optimal 1-planar graphs ⋮ Minimal Obstructions for 1-Immersions and Hardness of 1-Planarity Testing ⋮ Planar graphs having no proper 2-immersions in the plane. I ⋮ Note on improper coloring of $1$-planar graphs ⋮ Edge Partitions and Visibility Representations of 1-planar Graphs

This page was built for publication: A linear-time algorithm for 7-coloring 1-plane graphs