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
-
4:33:48
tacetmort3m
1 day ago🔴 LIVE - THE ZONE KEEPS PULLING ME BACK - STALKER 2 - PART 15
44.3K12 -
22:45
Brewzle
15 hours agoI Went Drinking In A Real Bourbon Castle
29.4K3 -
48:36
PMG
1 day ago $2.16 earned"Parkland Parent Speaks Out On Kamala Harris Using Victims"
22.4K3 -
4:06
The Lou Holtz Show
13 hours agoCoach Lou Holtz’s Heartfelt Christmas Message 🎄 | Family, Faith & Notre Dame Spirit 💚 #christmas
16.8K -
51:35
Dr Steve Turley
1 day ago $18.37 earnedROSEANNE BARR - Her Journey, TRUMP, and the MAGA GOLDEN AGE! [INTERVIEW]
52.1K51 -
57:38
The Tom Renz Show
11 hours agoMerry Christmas - The Tom Renz Show Christmas
89.6K17 -
2:59:10
Wendy Bell Radio
22 hours agoThe Bridge Too Far
167K301 -
1:03:45
Donald Trump Jr.
1 day agoHappy Festivus: Airing Our Grievances and Stopping The Swamp w/Sean Davis | TRIGGERED Ep.201
427K546 -
1:30:30
Game On!
1 day ago $7.99 earnedTop 5 things you need to know for Sports Christmas!
74.7K5 -
1:58:10
Robert Gouveia
1 day agoMatt Gaetz REJECTS Report, Sues Committee; Luigi Fan Club Arrives; Biden Commutes; Festivus Waste
298K234