Discrete Mathematics 2 + Configurations Lectures

Graph Colorings and Matchings

presenter: Primož Potočnik, Fakulteta za matematiko in fiziko, Faculty of Electrical Engineering, University of Ljubljana

Categories

Top: Mathematics: Graph Theory

You might be experiencing some problems with Your Video player.

*Slides*
0:00	Lesson No. 3: Graphs continued
0:36	Vertex-colorings of graphs
2:27	Vertex-colorings - examples
3:10	... more examples
5:04	Graphs with x ≤ 2 - 1
6:34	... more examples
6:36	Graphs with x ≤ 2 - 1
7:02	Graphs with x ≤ 2 - 2
10:42	Characterization of bipartite graphs
11:16	Cliques
12:06	Maximal clique
12:20	Cliques
12:45	Maximal clique
13:24	Cliques
13:47	Maximal clique
15:09	The Brooks theorem
16:19	Proof of the Brooks theorem - 1
17:56	Proof of the Brooks theorem - 2
18:19	Proof of the Brooks theorem - 1
18:56	Proof of the Brooks theorem - 2
19:27	Proof of the Brooks theorem - 3
19:39	Proof of the Brooks theorem - 4
19:51	Proof of the Brooks theorem - 5
19:56	Proof of the Brooks theorem - 6
20:15	Proof of the Brooks theorem - 7
20:32	Proof of the Brooks theorem - 8
21:14	Proof of the Brooks theorem - killing unessential greens
25:41	Proof of the Brooks theorem - pushing the green color - 1
29:33	- Questions
32:57	The proof of Brook's theorem - reduction to regular graphs
35:48	The proof of Brook's theorem - the 3-connected case - 1
37:08	The proof of Brook's theorem - the 3-connected case - 2
38:20	The proof of Brook's theorem - the 3-connected case - 1
38:59	The proof of Brook's theorem - the 3-connected case - 2
39:32	The proof of Brook's theorem - the 3-connected case - 3
39:46	The proof of Brook's theorem - κ ≤ 2
40:18	...κ = 1
41:01	...κ = 2

Lecture rating

People found this lecture:
Worth seeing
because it is:
Valuable and informative
Well presented
Easily understandable
Acceptably recorded
You need to login to cast your vote.

Report a problem or upload files

If you have found a problem with this lecture or would like to send us extra material, articles, exercises, etc., please use our ticket system to describe your request and upload the data.
Enter your e-mail into the 'Cc' field, and we will keep you updated with your request's status.