Extended Abstracts Summer 2015 by Josep Díaz Lefteris Kirousis Luis Ortiz-Gracia & Maria Serna

Author:Josep Díaz, Lefteris Kirousis, Luis Ortiz-Gracia & Maria Serna
Language: eng
Format: epub
Publisher: Springer International Publishing, Cham

The integer N in the above theorem is referred to as a cut-off point because it marks the onset of subexponential probability for the number of steps (calls of Resample) that M-Algorithm takes before it stops. Clearly, when the algorithm stops we have found an assignment such that none of the events occurs. And since this happens with probability close to 1 for large enough n, Theorem 1 indeed easily follows.

We used our alternative approach to a particular coloring problem, namely the acyclic edge coloring. The entropy compression method had been used in Esperet–Parreau [4] to find bounds for the acyclic chromatic index, the least number of colors needed to properly color the edges of a graph so that no bichromatic cycle exists. Our approach leads to a direct and simple probabilistic analysis giving the upper bound of for the acyclic chromatic index, improving the bound of given by Esperet and Parreau. We also improve their bounds for graphs with bounded girth.

Theorem 3

Assuming , the maximum degree of the graph G, is constant, and given the availability of at least colors, there exists a coloring of the edges such that no two adjacent ones have the same color and no cycle is colored with only two colors. Furthermore, such a coloring can be found by our algorithm (see Fig.  2 ) almost surely.

Fig. 2The coloring algorithm

Download

Copyright Disclaimer:
This site does not store any files on its server. We only index and link to content provided by other sites. Please contact the content providers to delete copyright contents if any and email us, we'll remove relevant links or contents immediately.