I have a problem like this:

An undirected graph $G$ has width $w$ if the vertices can be arranged in a sequence $v_1, v_2, v_3, ..., v_n$ such that each vertex $v_i$ is joined by an edge to at most $w$ preceding vertices. (Vertex $v_j$ precedes $v_i$ if $j$ < $i$.) Use induction to prove that every graph with width at most $w$ is $(w + 1)$-colorable.


I think I could do the proof in general, but before that, I would need to understand what graph width is. My problem is, I can't really visualize how a graph that satisfies the property from above (the vertices can be arranged in the given sequence) would look like. I also read the definition of Treewidth, but it wasn't clear for me if that's even the same thing as in the problem.

How would a graph look like that satisfies the property from the problem description?

  • 1
    $\begingroup$ A graph of width $w$ is one you can draw this way: Draw a vertex $v_1,$ then draw a vertex $v_2,$ then draw edges joining $v_2$ to at most $w$ of the previously drawn vertices, then draw a vertex $v_3$ and edges joining $v_3$ to at most $w$ of the previous vertices, and so on. In other words, exactly what the definition says. I don't understand your question. $\endgroup$ – bof Aug 23 '17 at 9:27

Some intuition as to why it's called width.

Think of vertices as cities and edges as lanes. Say a $v_j$ is a larger city than $v_i$ if $j>i$.

You want to get from $v_n$ to $v_1$ and never want to travel from a city to a larger one. That is, during your journey, you always want to travel to a smaller city from the one you are currently in.

Now, the statement that the graph has width w means that at every leg of your journey, you have at most $w$ roads to choose from. If edges are lanes, the width is the maximum number of lanes connecting a city to all cities smaller than it.

So $w$ basically bounds the number of choices you have at each stage.

Why does this relate to colouring? Hint:

Think choices. Start colouring from $v_1$ to $v_n$ and while colouring $v_k$ see how many choices we have while going to a smaller city.

  • $\begingroup$ I didn't know it was called width, I thought it was called degeneracy. $\endgroup$ – bof Aug 23 '17 at 10:33
  • $\begingroup$ Wikipedia says "Degeneracy is also known as the k-core number, width, and linkage, and is essentially the same as the coloring number or Szekeres-Wilf number " $\endgroup$ – Globe Theatre Aug 23 '17 at 10:38
  • $\begingroup$ Thank you that is a great example and helped me visualizing how such a graph looked like. $\endgroup$ – Max Aug 24 '17 at 2:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.