coloring a graph with minimum colors

Question

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

p₁ = (v₁, p₁₁,p₁₂,v₂)
p₂ = (v₁, p₂₁,p₂₂,v₂)
...
p_n = (v₁, p_n1,p_n2,v₂)

(p₁₁,p₁₂ are vertices of the path, the path has four vertices)

p_i means a path, p_i1 and p_i2 are the two vertices between v₁ and v₂.

There mustn't exist two paths p_i and p_j such that c(p_i1) = c(p_j1) and c(p_i2) = c(p_j2), where c(v) means the color of vertex v.

Simply speaking, the paths between v₁ and v₂ 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.

Answer 1

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 x² 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 ^xP₂ permutations can be generated. That is x²-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)