Starting from:

$30

CSDS455-Homework 18 Solved

Problem 1: Let G be a chordal graph. Let G0 be the graph created by taking G and performing a sequence of edge contractions. Prove that G0 is also chordal.

Problem 2: Let G be a planar graph. Prove that any minor of a planar graph must also be planar. (Don’t use Kuratowski’s Theorem.)

Problem 3: Prove that if any graph G with χ(G) ≥ k contains a Kk minor, then any graph G0 with χ(G0) ≥k− 1 must contain a Kk−1 minor.

Problem 4: Use induction on the number of vertices of G to prove that if G does not contain a K4 minor then G is 3-colorable.

More products