coloring a graph with minimum colors

3
votes

I want to color a graph such that for any vertex v1 and v2, if there are n paths between them:

p1 = (v1, p11,p12,v2)
p2 = (v1, p21,p22,v2)
...
pn = (v1, pn1,pn2,v2)

(p11,p12 are vertices of the path, the path has four vertices)

pi means a path, pi1 and pi2 are the two vertices between v1 and v2.

There mustn't exist two paths pi and pj such that c(pi1) = c(pj1) and c(pi2) = c(pj2), where c(v) means the color of vertex v.

Simply speaking, the paths between v1 and v2 should be distinguishable.

Our goal is to minimize the number of colors.

Is there a coloring algorithm satisfying above conditions? Star coloring definitely satisfies the conditions but it needs more colors.

1
algorithmgraph
Are we talking about simple paths only? If we can revisit vertices, then the problem is quite easily reducible to the usual coloring problem. - John Dvorak
I don't understand this syntax, p1 = (v1, p11,p12,v2). p1 being a path connecting to vertices v1 and v2, but what is this two other arguments in the middle, what do they even mean for you? - Shane Hsu
@ShaneHsu I read that as p1 = (v1, v11, v12, ..., v2). If that's the correct interpretation, it's an interesting problem. If not, it's a different (interesting?) problem - John Dvorak
@ShaneHsu I consider your question resolved (noting that c(pi2) is a vertex color). I'm still wondering about mine. If any walk is available, it greatly simplifies the problem, and I can write an answer. If not, I can only give an upper bound. - John Dvorak
Do you have the problem description in Chinese, paste it to pastebin and I can maybe better describe it for you. - Shane Hsu

1 Answers

1
votes

This is my answer given how I understood your question. You are trying to find out the minimum number of colours you can use to connect N 2-vertex paths.

Try solving the opposite : given x colours how many unique paths can you generate. It was not clear from question whether first and second vertex can be of same color so I will take the two possibilities:

  1. Same colour allowed (permutation with replacement)

    Given x colours max x2 permutations can be generated. So N paths will need at least √N colours.

    For colours = RGB vertices = RR,RG,RB,GR,GG,GB,BR,BG,BB

  2. Same colour not allowed (permutation without replacement)

    Given x colours max xP2 permutations can be generated. That is x2-x ≥ N. Solving the quadratic inequality will give you

    x ≥ (1 ± √(1 + 4 N))/2

    x = floor((1 + √(1 + 4 N))/2)

    For colours = RGB vertices = RG,RB,GR,GB,BR,BG (Given 7 paths you need 4 colours)