Pustaka Ilmiah Universitas Padjadjaran

Abstrak

Fractional Colorings in The Mycielski Graphs

In this paper, we will investigate the results of graph coloring by Michael Larsen, James Propp and Daniel Ullman 1995. Namely, “fractional chromatic number of Mycielski Graf,” that the fractional clique number of a graph G bounded below by the number of clique integer, and it is equal to the fractional chromatic number, which is bounded above by the number of chromatic integer. In other words, ()< f()= ()< () Given this relationship, giving rise to a question whether the difference ()- () and ()- () can be made arbitrary large. The question then will be proved in the affirmative, with the order of the graph to show the differences between them are increased without limit. Proof to determine the fractional coloring and the fractional chromatic number, will be shown in two different ways: first intuitively, combinatorial way marked in relation to with graph homomorphisms, and then in relation to with an independent set, with calculations using linear programming. In this second context, will be defined fractional clique, and see how this relates to fractional coloring. Relationship between coloring fractions and fractional clique is the key proof of Larsen, Propp, and Ullman.