CODEWITHSUNDEEP
algorithmgraph
Xinli Niu
Xinli Niu

Reputation: 501

coloring a graph with minimum colors

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.

Upvotes: 3

Views: 2147

Answers (1)

user568109
user568109

Reputation: 48013

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)

Upvotes: 1

Related Questions