Balanced polychromatic 2-coloring of triangulations

DOI10.1007/S00373-021-02420-8MaRDI QIDQ2062902zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

triangulationquadrangulationbisectionpolychromatic coloring

Mathematics Subject Classification ID

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

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

Cites work

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

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)