Fractional colorings and the fractional chromatic number of graphs | graph theory | advanced level

Episode 56.

Fractional colorings and the fractional chromatic number of graphs | graph theory | advanced level.

Branch of mathematics: graph theory.
Difficulty level: advanced.

Definition. A fractional $a:b$-coloring of graph $G$ is an assignment of a set of $b$ colors to each vertex of $G$ out of the total of $a$ colors such that for any two adjacent vertices their sets of colors are disjoint.
Definition. A graph is said to be fractionally $a:b$-colorable if there exists a fractional $a:b$-coloring of it.
Definition. The fractional chromatic number of graph $G$, denoted by $\Chi_f(G)$, is $inf_{a,b, \text{$G$ is fractionally $a:b$-colorable}}{\frac{a}{b}}$.

Theorem. For any graph $G$, the fractional chromatic number is less or equal than the chromatic number: $\Chi_f(G) \leq \Chi(G)$.

Theorem. There exists a graph with fractional chromatic number strictly less than the chromatic number.
An example of such a graph is $C_5$, the cycle of length 5. We have $\Chi_f(C_5) \leq \frac{5}{2} < 3 = \Chi(C_5)$.

Mathematics. Discrete Mathematics. Combinatorics. Graph theory.
#Mathematics #DiscreteMathematics #Combinatorics #GraphTheory

The same video on YouTube:
https://youtu.be/0mPbj8vkJek

The same video on Telegram:
https://t.me/mathematical_bunker/80