Applications Of Fractional Chromatic Numbers In Mycielski’s Graphs

Abstract

This chapter explores the applications of Fractional Chromatic Numbers and transformative properties of Mycielski's graph construction, shedding light on the relationships between fractional chromatic numbers, clique numbers, and chromatic numbers. The Mycielski transformation, applied iteratively to a starting graph, generates a sequence of graphs, each revealing intriguing patterns in these graph parameters. We prove that, for any graph G, the resulting graph µ(G) exhibits distinct properties:

(a) The clique number ω(µ(G)) remains equal to the original graph's ω(G) for all iterations.

(b) The chromatic number χ(µ(G)) increases by one compared to the chromatic number of the previous iteration, i.e., χ(µ(G)) = χ(G) + 1.

(c) The fractional chromatic number χ_F(µ(G)) increases by a fraction dependent on the original graph's fractional chromatic number χ_F(G).