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
-
2:14:02
The Quartering
6 hours agoEpstein Files FINALLY Arrive, Zelensky CRAWLS Back & Trump Cuts Off, Oscars Sink To New Low & More
96.4K45 -
57:11
Russell Brand
5 hours agoBREAK BREAD EP. 16 - SEAN FEUCHT
86.4K5 -
12:20
SLS - Street League Skateboarding
6 hours agoYuto Horigome's Top Moments of 2024! All The 9's 🔥
52.2K2 -
1:26:52
The Officer Tatum
5 hours agoLIVE: Leftists RAGE As Trump HALTS Aid to Ukraine + More | Officer Tatum Show Ep 72
68.3K35 -
1:59:43
The Charlie Kirk Show
6 hours agoTariffs and Trade Wars + Peace in Ukraine? + SOTU Preview | Carney, Schweizer | 3.4.25
122K27 -
43:54
Ben Shapiro
6 hours agoEp. 2150 - Trump’s STATE OF THE UNION Pledge
75.1K49 -
1:26:36
Russell Brand
7 hours agoZelensky’s Misstep: Why It Backfired & What Comes Next – SF547
131K37 -
56:23
The Dan Bongino Show
9 hours agoThe Momentum Keeps Shifting (Ep. 2435) - 03/04/2025
866K1.34K -
1:53:44
Benny Johnson
7 hours ago🚨Trump Attorney General Drops a New ‘TRUCKLOAD’ of Epstein Evidence | Kash FIRES FBI Head, Cover-Up
152K259 -
59:30
The Rubin Report
7 hours agoMarco Rubio Destroys CNN Host’s Narrative with Facts in Only 1 Minute
112K90