Chapter 11 Simple Graphs452
Problem 11.36.
A sequence of vertices of a graph haswidthwiff each vertex is adjacent to at most
wvertices that precede it in the sequence. A simple graph,G, had widthwif there
is a width-wsequence of all its vertices.
(a)Explain why the width of a graph must obviously be at least the minimum
degree of its vertices.
(b)Prove that if a finite graph has widthw, then there is a width-wsequence of
all it vertices that ends with a minimum degree vertex.
(c)Describe a simple algorithm to find the minimum width a graph.Problem 11.37.
LetGbe a simple graph whose vertex degrees are allk. Prove by induction on
number of vertices that if every connected component ofGhas a vertex of degree
strictly less thank, thenGisk-colorable.
Problem 11.38.
A basic example of a simple graph with chromatic numbernis the complete graph
onnvertices, that is .Kn/Dn. This implies that any graph withKnas a subgraph
must have chromatic number at leastn. It’s a common misconception to think that,
conversely, graphs with high chromatic number must contain a large complete sub-
graph. In this problem we exhibit a simple example countering this misconception,
namely a graph with chromatic number four that contains notriangle—length three
cycle—and hence no subgraph isomorphic toKnforn 3. Namely, letGbe the
11 -vertex graph of Figure 11.27. The reader can verify thatGis triangle-free.
(a)Show thatGis 4-colorable.(b)Prove thatGcan’t be colored with 3 colors.Problem 11.39.
This problem will show that 3-coloring a graph is just as difficult as finding a sat-
isfying truth assignment for a propositional formula. The graphs considered will
all be taken to have three designatedcolor-verticesconnected in a triangle to force
them to have different colors in any coloring of the graph. The colors assigned to
the color-vertices will be calledT;FandN.