Extension to 3-Colorable Triangulations

DOI10.1137/17M1135505zbMath1419.05078OpenAlexW2965457632MaRDI QIDQ5232159

Kenta Noguchi, Kenta Ozeki, Atsuhiro Nakamoto

Publication date: 29 August 2019

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/17m1135505

zbMATH Keywords

polychromatic coloringeven triangulationfundamental group of a surface3-colorable triangulation

Mathematics Subject Classification ID

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

Related Items (1)

The choice number versus the chromatic number for graphs embeddable on orientable surfaces

Cites Work

• Polychromatic 4-coloring of cubic even embeddings on the projective plane
• Polychromatic 4-coloring of cubic bipartite plane graphs
• \(N\)-flips in even triangulations on the torus and Dehn twists preserving monodromies
• A short proof of Chvatal's Watchman Theorem
• The prison yard problem
• Chromatic numbers and cycle parities of quadrangulations on nonorientable closed surfaces
• Three-coloring graphs embedded on surfaces with all faces even-sided
• Circuit Double Cover of Graphs
• Full 4-colorings of 4-regular maps
• A new proof of 3-colorability of Eulerian triangulations
• Cyclic 4-Colorings of Graphs on Surfaces
• Extension to Even Triangulations
• Polychromatic colorings of bounded degree plane graphs
• A Graph-Coloring Result and Its Consequences for Polygon-Guarding Problems
• On Even Triangulations of 2-Connected Embedded Graphs
• A Contribution to the Theory of Chromatic Polynomials
• Polychromatic colorings of plane graphs
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Extension to 3-Colorable Triangulations