4
$\begingroup$

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.

Source

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?

$\endgroup$
1
  • 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
    Commented Aug 23, 2017 at 9:27

1 Answer 1

3
$\begingroup$

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.

$\endgroup$
3
  • 1
    $\begingroup$ I didn't know it was called width, I thought it was called degeneracy. $\endgroup$
    – bof
    Commented Aug 23, 2017 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$ Commented Aug 23, 2017 at 10:38
  • $\begingroup$ Thank you that is a great example and helped me visualizing how such a graph looked like. $\endgroup$
    – BMBM
    Commented Aug 24, 2017 at 2:48

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .