Balanced polychromatic 2-coloring of triangulations

DOI10.1007/S00373-021-02420-8zbMATH Open1486.05082OpenAlexW4200269784MaRDI QIDQ2062902FDOQ2062902

Authors: Yoshihiro Asayama, Naoki Matsumoto 

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

Recommendations

• Polychromatic colorings of hypergraphs with high balance
• Balanced coloring of bipartite graphs
• scientific article; zbMATH DE number 1759407
• On balanced colorings of hypergraphs
• Balanced two-colorings of finite sets in the cube
• Balanced colourings of strongly regular graphs
• Polychromatic colorings of bounded degree plane graphs
• Good and nice colorings of balanced hypergraphs
• Balancing connected colourings of graphs

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

• Graph theory
• Reducibility among combinatorial problems
• Graphs on surfaces
• A Graph-Coloring Result and Its Consequences for Polygon-Guarding Problems
• Bounds on the max and min bisection of random cubic and random 4-regular graphs
• Polynomial Time Approximation Schemes for MAX-BISECTION on Planar and Geometric Graphs
• Polychromatic 4-coloring of cubic bipartite plane graphs
• Polychromatic colorings of bounded degree plane graphs
• Polychromatic 4-coloring of cubic even embeddings on the projective plane
• Generating even triangulations of the projective plane
• Inductive definition of two restricted classes of triangulations
• Polychromatic colorings of rectangular partitions
• The Grötzsch theorem for the hypergraph of maximal cliques
• Polychromatic colorings of plane graphs
• Polychromatic 4-coloring of guillotine subdivisions
• Worst-case-optimal algorithms for guarding planar graphs and polyhedral surfaces
• MAX-CUT and MAX-BISECTION are NP-hard on unit disk graphs
• An improved kernel for max-bisection above tight lower bound
• Extension to Even Triangulations
• Generating even triangulations on the torus
• Spanning quadrangulations of triangulated surfaces
• Generating even triangulations on the Klein bottle
• Spanning bipartite quadrangulations of even triangulations

Cited In (4)

• Partitioning 2-edge-colored graphs by monochromatic paths and cycles
• 3-polychromatic quadrangulations on surfaces
• Extending triangulations of the 2-sphere to the 3-disk preserving a 4-coloring
• Triad colorings of triangulations on closed surfaces

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

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