Balanced polychromatic 2-coloring of triangulations
type: Item
instance of: scholarly article
title: Balanced polychromatic 2-coloring of triangulations
zbMATH Open document ID: 1486.05082
author: Yoshihiro Asayama
author: Naoki Matsumoto
published in: Graphs and Combinatorics
publication date: 2022-01-03T00:00:00Z
review text: For a given graph \(G\), a polychromatic \(k\)-coloring of a graph \(G\) is a (not necessarily proper) vertex coloring of \(G\) such that all \(k\) colors appear on the boundary of each face of \(H\). A graph on a closed surface has a balanced polychromatic \(2\)-coloring which is a bisection, i.e., the difference in size of each color class is at most one. In this paper, the authors show that every \(3\)-colorable triangulation has a balanced polychromatic 2-coloring, and they construct an infinite family of triangulations \(G\) with order \(n\) on the sphere such that for every polychromatic \(2\)-coloring of \(G\), the size of color classes differs at least \(n/3-2\). This paper also proposes a conjecture that every triangulation on the sphere has a polychromatic \(2\)-coloring whose size of color classes differs at most one-third of the number of vertices. The authors verify the conjecture for two classes of graphs, i.e., triangulations on the plane of order \(n\ge 4\) with the minimum degree at least \(4\), and planar \(3\)-trees of order \(n\ge 4\) which is a planar graph obtained from the complete graph of order \(4\) on the plane by repeatedly inserting a vertex of degree \(3\) in a triangular face and joining it to vertices on the boundary of the corresponding face.
reviewed by: Yongtang Shi
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 05C10
zbMATH DE Number: 7451450
zbMATH Keywords: polychromatic coloring
zbMATH Keywords: bisection
zbMATH Keywords: triangulation
zbMATH Keywords: quadrangulation
MaRDI profile type: Publication
full work available at URL: s00373-021-02420-8
OpenAlex ID: W4200269784
cites work: Polychromatic colorings of plane graphs
cites work: Generating even triangulations on the Klein bottle
cites work: Inductive definition of two restricted classes of triangulations
cites work: Q5422499
cites work: Worst-case-optimal algorithms for guarding planar graphs and polyhedral surfaces
cites work: Bounds on the max and min bisection of random cubic and random 4-regular graphs
cites work: MAX-CUT and MAX-BISECTION are NP-hard on unit disk graphs
cites work: Polychromatic colorings of rectangular partitions
cites work: An improved kernel for max-bisection above tight lower bound
cites work: A Graph-Coloring Result and Its Consequences for Polygon-Guarding Problems
cites work: Polychromatic 4-coloring of guillotine subdivisions
cites work: Polychromatic 4-coloring of cubic bipartite plane graphs
cites work: Polychromatic colorings of bounded degree plane graphs
cites work: Polynomial Time Approximation Schemes for MAX-BISECTION on Planar and Geometric Graphs
cites work: Reducibility among Combinatorial Problems
cites work: Polychromatic 4-coloring of cubic even embeddings on the projective plane
cites work: Spanning quadrangulations of triangulated surfaces
cites work: Generating even triangulations on the torus
cites work: Graphs on surfaces
cites work: The Grötzsch theorem for the hypergraph of maximal cliques
cites work: Extension to Even Triangulations
cites work: Spanning bipartite quadrangulations of even triangulations
cites work: Generating even triangulations of the projective plane
DOI: 10.1007/S00373-021-02420-8
Recommended article: Polychromatic colorings of hypergraphs with high balance
Recommended article: Balanced coloring of bipartite graphs
Recommended article: Q4536356
Recommended article: On balanced colorings of hypergraphs
Recommended article: Balanced two-colorings of finite sets in the cube
Recommended article: Balanced colourings of strongly regular graphs
Recommended article: Polychromatic colorings of bounded degree plane graphs
Recommended article: Good and nice colorings of balanced hypergraphs
Recommended article: Balancing connected colourings of graphs
description: scientific article; zbMATH DE number 7451450