Graph Theory - Lecture 17 - Kuratowsky''s Theorem Notes

: Graph Theory - Lecture 17 - Kuratowsky''s Theorem Notes

 Page 1


Graph Theory: Lecture No. 17
Graph Theory: Lecture No. 17
L. Sunil Chandran
Computer Science and Automation,
Indian Institute of Science, Bangalore
Email: sunil@csa.iisc.ernet.in
Page 2


Graph Theory: Lecture No. 17
Graph Theory: Lecture No. 17
L. Sunil Chandran
Computer Science and Automation,
Indian Institute of Science, Bangalore
Email: sunil@csa.iisc.ernet.in
Graph Theory: Lecture No. 17
A planar graph is 6-colorable.
Page 3


Graph Theory: Lecture No. 17
Graph Theory: Lecture No. 17
L. Sunil Chandran
Computer Science and Automation,
Indian Institute of Science, Bangalore
Email: sunil@csa.iisc.ernet.in
Graph Theory: Lecture No. 17
A planar graph is 6-colorable.
Graph Theory: Lecture No. 17
A planar graph is 5-colorable.
Page 4


Graph Theory: Lecture No. 17
Graph Theory: Lecture No. 17
L. Sunil Chandran
Computer Science and Automation,
Indian Institute of Science, Bangalore
Email: sunil@csa.iisc.ernet.in
Graph Theory: Lecture No. 17
A planar graph is 6-colorable.
Graph Theory: Lecture No. 17
A planar graph is 5-colorable.
Graph Theory: Lecture No. 17
Kuratowsky's Theorem: The following
assertions are equivalent for graphs G:
(1) G is planar
(2) G contains neither K
5
nor K
3;3
as a
topological minor.
(3) G contains neither K
3;3
or K
5
as a minor
Page 5


Graph Theory: Lecture No. 17
Graph Theory: Lecture No. 17
L. Sunil Chandran
Computer Science and Automation,
Indian Institute of Science, Bangalore
Email: sunil@csa.iisc.ernet.in
Graph Theory: Lecture No. 17
A planar graph is 6-colorable.
Graph Theory: Lecture No. 17
A planar graph is 5-colorable.
Graph Theory: Lecture No. 17
Kuratowsky's Theorem: The following
assertions are equivalent for graphs G:
(1) G is planar
(2) G contains neither K
5
nor K
3;3
as a
topological minor.
(3) G contains neither K
3;3
or K
5
as a minor
Graph Theory: Lecture No. 17
If ¢(X)· 3 then every MX contains a TX.
Thus every minor with maximum degree at
most 3 is also its topological minor.
Read More
Use Code STAYHOME200 and get INR 200 additional OFF
Use Coupon Code

Download free EduRev App

Track your progress, build streaks, highlight & save important lessons and more!