Polychromatic colorings of bounded degree plane graphs

DOI10.1002/JGT.20357MaRDI QIDQ3633009zbMATH OpenOpenAlexFDO

Authors Elad Aigner-Horev, Roi Krakovski

Publication date 16 June 2009

Published in Journal of Graph Theory (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1002/jgt.20357

zbMATH Keywords

plane graphsbounded degree graphsvertex coloring with constraints on the faces

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Recommendations

• Polychromatic colorings of plane graphs
• A note on polychromatic colorings of plane graphs
• On maximum face-constrained coloring of plane graphs with no short face cycles.
• Polychromatic 4-coloring of cubic bipartite plane graphs
• Unique-maximum coloring of plane graphs

Cites work

• scientific article; zbMATH DE number 854567 (Why is no real title available?)
• A Graph-Coloring Result and Its Consequences for Polygon-Guarding Problems
• GUARDING RECTANGULAR PARTITIONS
• Polychromatic colorings of plane graphs
• Polychromatic colorings of rectangular partitions
• The Grötzsch theorem for the hypergraph of maximal cliques
• Worst-case-optimal algorithms for guarding planar graphs and polyhedral surfaces

Cited in

(18)

• Box-respecting colorings of n-dimensional guillotine-partitions
• On maximal cycles or triangular planar polygonal graphs and their coloring
• Polychromatic colorings of arbitrary rectangular partitions
• Face-hitting dominating sets in planar graphs
• Polychromatic colorings of plane graphs
• Extension to 3-colorable triangulations
• Colouring planar graphs with three colours and no large monochromatic components
• Polychromatic 4-coloring of guillotine subdivisions
• An abstract approach to polychromatic coloring: shallow hitting sets in ABA-free hypergraphs and pseudohalfplanes
• Polychromatic colorings of rectangular partitions
• 3-polychromatic quadrangulations on surfaces
• On maximum face-constrained coloring of plane graphs with no short face cycles.
• Facially-constrained colorings of plane graphs: a survey
• A note on polychromatic colorings of plane graphs
• Polychromatic 4-coloring of cubic bipartite plane graphs
• Balanced polychromatic 2-coloring of triangulations
• Facial achromatic number of triangulations on the sphere
• Polychromatic 4-coloring of cubic even embeddings on the projective plane

This page was built for publication: Polychromatic colorings of bounded degree plane graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3633009)