Premium Only Content

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
-
1:28:42
Redacted News
6 hours agoBREAKING! SOMETHING BIG IS HAPPENING IN EUROPE ALL OUT WAR IS COMING AGAINST RUSSIA, TRUMP FURIOUS
121K286 -
47:50
Candace Show Podcast
6 hours agoBREAKING: Judge Makes Statement Regarding Taylor Swift's Text Messages. | Candace Ep 155
113K117 -
1:14:23
Josh Pate's College Football Show
3 hours ago $0.29 earnedCFB’s Most Hated Teams | FSU & Clemson Future | Big Ten Win Totals | Star Rankings Overrated?
14.5K -
1:33:47
CatfishedOnline
5 hours agoGoing Live With Robert - Weekly Recap
27.8K -
55:18
LFA TV
1 day agoEurope’s Sudden Turn Against America | TRUMPET DAILY 3.6.25 7PM
32.2K3 -
4:21
Tundra Tactical
4 hours ago $2.12 earnedPam Bondi MUST Enforce Due Process NOW!
23.7K1 -
56:42
VSiNLive
5 hours agoFollow the Money with Mitch Moss & Pauly Howard | Hour 1
48K1 -
1:05:32
In The Litter Box w/ Jewels & Catturd
1 day agoShalom Hamas | In the Litter Box w/ Jewels & Catturd – Ep. 756 – 3/6/2025
103K37 -
1:23:00
Sean Unpaved
7 hours ago $3.19 earnedNFL Free Agency
53.4K4 -
18:25
Stephen Gardner
6 hours ago🔥The REAL REASON the Epstein Files are being HIDDEN | I CONFRONT Alan Dershowitz for details!
66.2K158