Balanced polychromatic 2-coloring of triangulations

DOI10.1007/s00373-021-02420-8zbMath1486.05082OpenAlexW4200269784MaRDI QIDQ2062902

Naoki Matsumoto, Yoshihiro Asayama

Publication date: 3 January 2022

Published in: Graphs and Combinatorics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00373-021-02420-8

zbMATH Keywords

triangulationquadrangulationbisectionpolychromatic coloring

Mathematics Subject Classification ID

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

Cites Work

• Unnamed Item
• Unnamed Item
• Polychromatic 4-coloring of cubic even embeddings on the projective plane
• Polychromatic 4-coloring of cubic bipartite plane graphs
• Inductive definition of two restricted classes of triangulations
• MAX-CUT and MAX-BISECTION are NP-hard on unit disk graphs
• Polychromatic 4-coloring of guillotine subdivisions
• 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
• Spanning quadrangulations of triangulated surfaces
• Generating even triangulations on the torus
• Bounds on the max and min bisection of random cubic and random 4-regular graphs
• An improved kernel for max-bisection above tight lower bound
• Generating even triangulations on the Klein bottle
• Extension to Even Triangulations
• Polychromatic colorings of bounded degree plane graphs
• Spanning bipartite quadrangulations of even triangulations
• A Graph-Coloring Result and Its Consequences for Polygon-Guarding Problems
• Reducibility among Combinatorial Problems
• Generating even triangulations of the projective plane
• Polynomial Time Approximation Schemes for MAX-BISECTION on Planar and Geometric Graphs
• Polychromatic colorings of plane graphs

This page was built for publication: Balanced polychromatic 2-coloring of triangulations