I am wondering about solutions to the graph colouring problem. I have looked around for quite a while and it seems that a bruteforce type approach is required.
The problem I have at hand is like this:
A network has n nodes. Each node is connected to the other (n  1) nodes. Assign integer numbers to all of the nodes and all of the connections in the network, so that each node and its (n  1) connections do not possess duplicate numbers. Of course, this must be done using at most n numbers for the entire network, which seems to be where the problem stops being trivial and starts becoming a juggling act of sorts. As far as I can tell, this is pretty much the same as the total coloring problem for an n vertex graph where all vertices are of degree (n  1).
Do you know if there is a nonbrute force solution to this type of problem?
This is not for work or school. It actually has to do with my flower bed next spring.
Graph Colouring (or something similar
Moderators: gmalivuk, Moderators General, Prelates
Re: Graph Colouring (or something similar
For odd n there is an easy to construct solution.
I hope that was clear.
I'll see if I can find a way to do even numbers later.
For even numbers a similar construction works too:
[edited to add picture]
Spoiler:
I hope that was clear.
For even numbers a similar construction works too:
Spoiler:
[edited to add picture]
Last edited by jaap on Tue Dec 01, 2009 8:07 pm UTC, edited 2 times in total.
 MartianInvader
 Posts: 808
 Joined: Sat Oct 27, 2007 5:51 pm UTC
Re: Graph Colouring (or something similar
Most graph coloring problems involve coloring just the vertices, and the edges indicate when two vertices can't have the same color. You might want to recast your problem in that framework by changing all of your "nodes" and "connections" into vertices, and then having exacting two edges coming out of each "connection" vertex: one going to each "node" vertex in that connection.
The graph you'd get out of this has n disjoint copies of the complete graph on n vertices, and each of these subgraphs is connected to each of the others by exactly one edge. So you kind of have a "complete graph on n complete graphs on n vertices" thing going on.
Let's see... If there's any justice in the world, you can do this symmetrically so that each "node" vertex gets a different color. So what you need is a way to assign to each "edge", a value based on the values of its nodes so that all the edges coming out of each node have different colors.
If we let S be the set {1,...,n}, this means you want a symmetric function f from S x S to S, such that:
[math]f(a,a) = a.
f(a,b) \neq a if b \neq a.
f(a,b) \neq f(a,c) for c \neq b.[/math]
This guarantees your edges are different from the nodes they touch, and that edges coming from the same node are different colors.
Hm... there's gotta be a simple way to do this, but I'm not seeing it right now. I'll think about it a little more.
The graph you'd get out of this has n disjoint copies of the complete graph on n vertices, and each of these subgraphs is connected to each of the others by exactly one edge. So you kind of have a "complete graph on n complete graphs on n vertices" thing going on.
Let's see... If there's any justice in the world, you can do this symmetrically so that each "node" vertex gets a different color. So what you need is a way to assign to each "edge", a value based on the values of its nodes so that all the edges coming out of each node have different colors.
If we let S be the set {1,...,n}, this means you want a symmetric function f from S x S to S, such that:
[math]f(a,a) = a.
f(a,b) \neq a if b \neq a.
f(a,b) \neq f(a,c) for c \neq b.[/math]
This guarantees your edges are different from the nodes they touch, and that edges coming from the same node are different colors.
Hm... there's gotta be a simple way to do this, but I'm not seeing it right now. I'll think about it a little more.
Let's have a fervent argument, mostly over semantics, where we all claim the burden of proof is on the other side!

 Posts: 272
 Joined: Thu Jul 09, 2009 9:26 am UTC
Re: Graph Colouring (or something similar
Having quickly drawn out the n=4 version, I'm pretty sure there's no way to do this so that each node gets a different number. I think it should be doable in general though.
How about this? Given the complete graph on n nodes, it's simple enough to find an edge colouring using n colours. Once the edges are coloured in, just go round the nodes and give them each whatever colour hasn't been used in the adjacent n1 edges. Done, no adjacent edges have the same colour and no node has the colour of an edge touching it.
Edit: Thinking about it, I'm not sure how simple it is to edge colour a complete graph with n colours. But it is certainly doable by Vizing's Theorem
How about this? Given the complete graph on n nodes, it's simple enough to find an edge colouring using n colours. Once the edges are coloured in, just go round the nodes and give them each whatever colour hasn't been used in the adjacent n1 edges. Done, no adjacent edges have the same colour and no node has the colour of an edge touching it.
Edit: Thinking about it, I'm not sure how simple it is to edge colour a complete graph with n colours. But it is certainly doable by Vizing's Theorem
Re: Graph Colouring (or something similar
Thanks for the help!
OK, so after reading these replies (all AWESOME), and a little sleep, I think I got it figured out a little...
I got this function:
[math]f(i, j) = \left\{
\begin{array}{l l}
j  (n  i + 1) & \text{if $j > n  i + 1$,}\\
j + i  1 & \text{if $j \leq n  i + 1$.}\\
\end{array} \right.[/math]
This gives these (ridiculously silly looking) matrices for [imath]n = 5[/imath] and [imath]n = 4[/imath]:
[math]\textbf{M}(5) = \left[ {\begin{array}{ccccc}
\bf{1} & 2 & 3 & 4 & 5\\
2 & \bf{3} & 4 & 5 & 1\\
3 & 4 & \bf{5} & 1 & 2\\
4 & 5 & 1 & \bf{2} & 3\\
5 & 1 & 2 & 3 & \bf{4}\\
\end{array} } \right] ,[/math]
[math]\textbf{M}(4) = \left[ {\begin{array}{cccc}
\bf{1} & 2 & 3 & 4\\
2 & \bf{3} & 4 & 1\\
3 & 4 & \bf{1} & 2\\
4 & 1 & 2 & \bf{3}\\
\end{array} } \right].[/math]
I take [imath]\textbf{M}_{ii}[/imath] to be the colour of the nodes (the nondiagonal entries produce a symmetric matrix, and represent the connections), and so in the case of an even number of nodes I'll have to go in and manually spruce up the last half of the diagonal in some way. This is not perfect, but it's better than nothing  thank you guys, this totally helped me out of my rut!!
OK, so after reading these replies (all AWESOME), and a little sleep, I think I got it figured out a little...
I got this function:
[math]f(i, j) = \left\{
\begin{array}{l l}
j  (n  i + 1) & \text{if $j > n  i + 1$,}\\
j + i  1 & \text{if $j \leq n  i + 1$.}\\
\end{array} \right.[/math]
This gives these (ridiculously silly looking) matrices for [imath]n = 5[/imath] and [imath]n = 4[/imath]:
[math]\textbf{M}(5) = \left[ {\begin{array}{ccccc}
\bf{1} & 2 & 3 & 4 & 5\\
2 & \bf{3} & 4 & 5 & 1\\
3 & 4 & \bf{5} & 1 & 2\\
4 & 5 & 1 & \bf{2} & 3\\
5 & 1 & 2 & 3 & \bf{4}\\
\end{array} } \right] ,[/math]
[math]\textbf{M}(4) = \left[ {\begin{array}{cccc}
\bf{1} & 2 & 3 & 4\\
2 & \bf{3} & 4 & 1\\
3 & 4 & \bf{1} & 2\\
4 & 1 & 2 & \bf{3}\\
\end{array} } \right].[/math]
I take [imath]\textbf{M}_{ii}[/imath] to be the colour of the nodes (the nondiagonal entries produce a symmetric matrix, and represent the connections), and so in the case of an even number of nodes I'll have to go in and manually spruce up the last half of the diagonal in some way. This is not perfect, but it's better than nothing  thank you guys, this totally helped me out of my rut!!
Re: Graph Colouring (or something similar
If n is even, then each color is shared by an even number of nodes. In particular, you can't make all nodes the same color. This can be shown by noticing that the number of nodes with an incident edge of that color is also even.
However, for even n, it's possible to make all nodes the same color. I'm not sure how the aesthetics of that would work out, but I thought I'd mention it anyway.
EDIT: I'm not sure what I was thinking when I said that was possible for all n.
However, for even n, it's possible to make all nodes the same color. I'm not sure how the aesthetics of that would work out, but I thought I'd mention it anyway.
EDIT: I'm not sure what I was thinking when I said that was possible for all n.
Last edited by Nitrodon on Wed Dec 02, 2009 3:19 am UTC, edited 1 time in total.
Re: Graph Colouring (or something similar
Jaap's picture for odd n is correct, and for even n, you can just plop a vertex in the middle of the diagram and for each color attach an edge of that color joining the center vertex to the one that is not represented by that edge color. So the subgraph of each color's edges in that particular graphical representation would be a bunch of parallel edges and then one perpendicular edge radiating from the center.
For even n, it's closely related to the problem of finding a roundrobin tournament between 2n players that can be accomplished in (2n1) rounds. (In graph theoretical terms, that is saying that [imath]K_2n[/imath] is 1factorable.) It should be simple enough to find charts of that online.
For even n, it's closely related to the problem of finding a roundrobin tournament between 2n players that can be accomplished in (2n1) rounds. (In graph theoretical terms, that is saying that [imath]K_2n[/imath] is 1factorable.) It should be simple enough to find charts of that online.
Re: Graph Colouring (or something similar
Tirian wrote:Jaap's picture for odd n is correct, and for even n, you can just plop a vertex in the middle of the diagram and for each color attach an edge of that color joining the center vertex to the one that is not represented by that edge color. So the subgraph of each color's edges in that particular graphical representation would be a bunch of parallel edges and then one perpendicular edge radiating from the center.
That does not quite work  you have added edges of the same colour as the nodes you are connecting them to. However, you have a graph now where every node has n edges that use n different colours. To fix it to satisfy the requirements, you then have to colour all the nodes with the (n+1)th colour.
Re: Graph Colouring (or something similar
Oh, I misunderstood. I couldn't figure why you were coloring the vertices too.
Right, then what you do is take Jaap's solution for odd n, plop down a center vertex, and then join that to every other vertex and color that new edge the color that was previously used for that vertex, and then color all of the vertices a new color. And there's no way to do better than that, because each vertex is incident upon as many colored elements as there are colors as it stands.
Right, then what you do is take Jaap's solution for odd n, plop down a center vertex, and then join that to every other vertex and color that new edge the color that was previously used for that vertex, and then color all of the vertices a new color. And there's no way to do better than that, because each vertex is incident upon as many colored elements as there are colors as it stands.
Who is online
Users browsing this forum: No registered users and 7 guests