Semi-balanced colorings of graphs.Semi-balanced colorings of graphs.

Access Restriction
Open

 Author Jansson, Jesper ♦ Tokuyama, Takeshi Source CiteSeerX Content type Text File Format PDF
 Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science Subject Keyword Semi-balanced Coloring ♦ Bipartite Graph ♦ Alternating Sequence ♦ Interesting Question ♦ Uniform Distribution ♦ Low-discrepancy Sequence ♦ Uniform Distri-bution ♦ General Structure ♦ Red Point ♦ Little Pity ♦ Natural Extension ♦ Uniformity Condition ♦ Blue Point ♦ Random Distribution ♦ Intermediate Sequence ♦ Natural Way ♦ Different 2-colorings Abstract Randomness often implies uniformity, but usually there exists a much more uniform distri-bution than a random distribution. An interesting question is how we can construct a strongly uniform distribution for a given structure. If we have n points on a line, it is easy to color points into red and blue such that the number of red points and blue points are almost same in each interval: Indeed, it suffices to color the points into red and blue to form an alternating sequence of two colors. The theory of low-discrepancy sequence is a problem to construct an alternating sequence on-line by changing color of points from red to bule one by one such that each intermediate sequence is almost “uniform”. It is an interesting question how we can generalize this fact to a more general structure, namely, a graph. Given a graph G = (V,E), a 2-coloring of G is a mapping π from V to {red, blue} such that π(x) = π(y) for every edge {x, y} in E. This is a natural extension of the alternating sequence. A graph has a 2-coloring if and only if it is bipartite; in fact, by symmetry, a bipartite graph always has two different 2-colorings. It is a little pity that only bipartite graphs can have 2-colorings, and we want to relax the condition such that the uniformity condition holds for a wider class of graphs. A natural way Educational Role Student ♦ Teacher Age Range above 22 year Educational Use Research Education Level UG and PG ♦ Career/Technical Study