Premium Only Content
Proper colorings and the chromatic number of graphs | graph theory | elementary level
Episode 51.
Proper colorings and the chromatic number of graphs | graph theory | elementary level.
Branch of mathematics: graph theory.
Difficulty level: elementary.
Definition. A coloring of vertices of a graph is said to be proper if any 2 adjacent vertices are colored in different colors.
Definition. A graph is said to be $r$-colorable if there exists a proper coloring of this graph in $r$ colors.
Definition. The chromatic number of a graph $G$, denoted by $\Chi(G)$, is the minimum number of colors for which there exists a proper coloring of the graph $G$.
The chromatic number of a graph is equal to 1 if and only if it has no edges.
The chromatic number of $K_n$ (the complete graph on $n$ vertices) is equal to $n$.
For all other graphs, the chromatic number is somewhere in between: $1 \leq \Chi(G) \leq n$, where $n$ is the number of vertices of $G$.
The bipartite graphs are 2-colorable and so their chromatic number is less or equal than 2.
Mathematics. Discrete Mathematics. Combinatorics. Graph theory.
#Mathematics #DiscreteMathematics #Combinatorics #GraphTheory
The same video on YouTube:
https://youtu.be/JCo_1v6cF0U
The same video on Telegram:
https://t.me/mathematical_bunker/75
-
53:37
Weberz Way
12 hours agoGOODBYE JOE, TRUMPS CABINET, LA FIRES, & KEEP TIKTOK
54 -
3:07:17
Alex Zedra
9 hours agoLIVE! New Game | Exorcism!??
27.1K3 -
6:00:06
SpartakusLIVE
12 hours agoThe Conqueror of Corona || Delta Force LATER
70.5K3 -
2:17:30
barstoolsports
15 hours ago$250k Winner Revealed With Final Votes And Reunion | Surviving Barstool S4 Finale
125K9 -
2:05:49
Kim Iversen
12 hours agoTikTok Ban BACKFIRES: Millions Flee To New App Showing The REAL China
114K160 -
1:35:12
Glenn Greenwald
14 hours agoCNN And Jake Tapper In Deep Trouble In Defamation Lawsuit: With Jonathan Turley; TikTok Ban, Trump's China Policy, And More With Arnaud Bertrand | SYSTEM UPDATE SHOW #390
107K81 -
12:24
Dan Bongino Show Clips
15 hours agoPresident Trump Full Interview - 01/16/25
133K300 -
1:27:39
Man in America
15 hours agoBig Pharma's Deadliest Lie is Being EXPOSED to the Masses w/ Jonathan Otto
93.2K39 -
1:40:08
Precision Rifle Network
1 day agoS4E2 Guns & Grub - Training Vs. Competition
46.7K2 -
58:27
Flyover Conservatives
1 day agoGarrett Ziegler Breaks Down Special Councilor’s Report on Hunter Biden. Insights for Trump’s Top Picks. | FOC Show
71.5K6