Graph Theory Help

[Matt_F]

-Give a method for constructing a tree T and ordering of its vertices so that when T's vertices are properly colored in the order specified, using a greedy algorithm, at least Delta(T) colors are used.


"I know that a tree is a graph that any two vertices are connected by one vertex, I also know that they can be colored in a minimum of 2 colors. That is about it"


Thank you.

 

[SlipEternal]

-Give a method for constructing a tree T and ordering of its vertices so that when T's vertices are properly colored in the order specified, using a greedy algorithm, at least Delta(T) colors are used.


"I know that a tree is a graph that any two vertices are connected by one vertex, I also know that they can be colored in a minimum of 2 colors. That is about it"


Thank you.

You can likely use a minimality/maximality argument to show that the method you choose will work. Note that every tree is bipartite (only graphs with odd cycles are not, and trees are acyclic). Not only are trees acyclic, they are maximally acyclic (adding any edge between two non-adjacent vertices will cause a cycle) and minimally connected (removing one edge will cause the graph to be disconnected). Also, your notation is specific to your course. In my graph theory course, \(\displaystyle \Delta(T)\) is the maximal degree of any vertex in the graph while \(\displaystyle \delta(T)\) is the minimal degree of any vertex in the graph. In the case of a tree, every tree with more than one vertex is 2-colorable. So, no matter what algorithm you use, a proper coloring will never have more than 2 colors. Now, if the coloring is not proper, then you need to give a better description of how one chooses whether to switch colors or not.

 

[Matt_F]

You can likely use a minimality/maximality argument to show that the method you choose will work. Note that every tree is bipartite (only graphs with odd cycles are not, and trees are acyclic). Not only are trees acyclic, they are maximally acyclic (adding any edge between two non-adjacent vertices will cause a cycle) and minimally connected (removing one edge will cause the graph to be disconnected). Also, your notation is specific to your course. In my graph theory course, \(\displaystyle \Delta(T)\) is the maximal degree of any vertex in the graph while \(\displaystyle \delta(T)\) is the minimal degree of any vertex in the graph. In the case of a tree, every tree with more than one vertex is 2-colorable. So, no matter what algorithm you use, a proper coloring will never have more than 2 colors. Now, if the coloring is not proper, then you need to give a better description of how one chooses whether to switch colors or not.

So what I think I am supposed to do is find a way to make the tree to have the maximum amount of colors using a greedy algorithm, Delta(T) in our course I am pretty sure is the maximal degree of any vertex. Everytime I try to draw this I just end up with a complete graph which I don't think is a tree.

 

[SlipEternal]

There are no three-cycles in a tree, so there can never be a case where the greedy algorithm will assign a third color to any vertex in a tree, no matter what order you supply the vertices. Here is an example: Consider a star. That is a single vertex connected to a lot of vertices. So, let's say we have 20 vertices. One vertex is in the middle with degree 19. Every other vertex is a leaf (connected to the single vertex in the middle). If you start with the leaves, they are all disconnected, so you only need one color. If you start with the center vertex, it takes one color, then all other vertices take a second color, but again, since there is no three-cycle, a third color will never be assigned. You can try taking 5 leaves, then the center vertex, then the rest of the leaves, and still you wind up with a two-coloring.

 

[Matt_F]

There are no three-cycles in a tree, so there can never be a case where the greedy algorithm will assign a third color to any vertex in a tree, no matter what order you supply the vertices. Here is an example: Consider a star. That is a single vertex connected to a lot of vertices. So, let's say we have 20 vertices. One vertex is in the middle with degree 19. Every other vertex is a leaf (connected to the single vertex in the middle). If you start with the leaves, they are all disconnected, so you only need one color. If you start with the center vertex, it takes one color, then all other vertices take a second color, but again, since there is no three-cycle, a third color will never be assigned. You can try taking 5 leaves, then the center vertex, then the rest of the leaves, and still you wind up with a two-coloring.

so It is not possible to color a tree with as many colors as the maximum out degree of any vertex with a greedy algorithm?

 

[SlipEternal]

If the maximum degree is 2, then it is possible. A tree with a maximum degree of 2 can also be called a path. So long as you only look at trees that also happen to be paths, you will succeed no matter what order you feed the vertices into the algorithm.

 

[Matt_F]

If the maximum degree is 2, then it is possible. A tree with a maximum degree of 2 can also be called a path. So long as you only look at trees that also happen to be paths, you will succeed no matter what order you feed the vertices into the algorithm.

so I can say in constructing your tree the maximum degree of any vertex can only be two and you will achieve the condition. If the the degree of any vertex is >2 then This condition will fail using a greedy algorithm

 

[SlipEternal]

so I can say in constructing your tree the maximum degree of any vertex can only be two and you will achieve the condition. If the the degree of any vertex is >2 then This condition will fail using a greedy algorithm

You can start at any vertex in a graph, label it \(\displaystyle v_1\) and look at its set of neighbors. Choose one and label it \(\displaystyle v_2\). Look at the set of neighbors of \(\displaystyle v_2\), but remove \(\displaystyle v_1\). Choose 1 and label it \(\displaystyle v_3\). At each step, look at the neighbors of the most recent vertex, but remove all previously used vertices. This will generate a path in whatever graph you are looking at. This path will be a tree that is a subgraph of whatever graph you are looking at, and it will be 2-colorable.