Polychromatic 4-coloring of cubic bipartite plane graphs

DOI10.1016/j.disc.2011.11.016zbMath1316.05044OpenAlexW1979228678MaRDI QIDQ409414

Matthew J. Katz, Atsuhiro Nakamoto, Roi Krakovski, Elad Aigner-Horev

Publication date: 13 April 2012

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

Full work available at URL: https://doi.org/10.1016/j.disc.2011.11.016

zbMATH Keywords

Eulerian triangulationpolychromatic coloringcubic bipartite plane graph

Mathematics Subject Classification ID

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

Related Items (13)

Cyclic 4-Colorings of Graphs on Surfaces ⋮ A new heuristic for detecting non-Hamiltonicity in cubic graphs ⋮ Facially-constrained colorings of plane graphs: a survey ⋮ Polychromatic 4-coloring of cubic even embeddings on the projective plane ⋮ Generating even triangulations on the Klein bottle ⋮ Polychromatic colorings of plane graphs ⋮ Generating even triangulations on the torus ⋮ Facial achromatic number of triangulations on the sphere ⋮ Balanced polychromatic 2-coloring of triangulations ⋮ Extension to 3-Colorable Triangulations ⋮ Polychromatic colorings of rectangular partitions ⋮ Polychromatic colorings of arbitrary rectangular partitions ⋮ A note on polychromatic colorings of plane graphs

Cites Work

• Unnamed Item
• An inductive definition of the class of 3-connected quadrangulations of the plane
• Polychromatic 4-coloring of guillotine subdivisions
• Polychromatic colorings of rectangular partitions
• A short proof of Chvatal's Watchman Theorem
• The Grötzsch theorem for the hypergraph of maximal cliques
• A combinatorial theorem in plane geometry
• Polychromatic colorings of bounded degree plane graphs
• A Graph-Coloring Result and Its Consequences for Polygon-Guarding Problems
• Polychromatic colorings of plane graphs

This page was built for publication: Polychromatic 4-coloring of cubic bipartite plane graphs