Thumbnail
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