# Paint graph ordered vertices

I have the following question: Given graph $$G=(V,E)$$ with given order on its vertices, I mean $$v_1 I need to find minimal colors ordered paining of the graph vertices s.t neighbor vertices don't have the same color, I mean: $$(v_1,v_2,...,v_j)$$ - painted in fist color and non of them are neighbors. $$(v_{j+1},...,v_l)$$ - painted in second color and non of them are neighbors. and so on.

The complexity needs to be $$O(V+E)$$. Anyone have an idea?

• What a "minimal colors ordered paining" ? Can you give a formal definition? Jun 13 '20 at 13:34
• I defined it in the next row - out goal is to paint the graph vertices with minimal colors while fulfill all the demands. Jun 14 '20 at 10:15
• That's vague and definitely not a formal definition. Can you write down precisely what condition your coloring should satisfy? In particular it is not clear how the coloring is related to the order of the vertices. To give an example, a formal definition for the usual graph coloring problem would be the following. Given a graph $G=(V,E)$, a $k$-coloring for $G$ is a function $c : V \to \{1, \dots, k\}$. $c$ valid if and only if $\forall (u,v) \in E, c(u) \neq c(v)$. The goal is to find a valid $k$-coloring for $G$ that minimizes $k$. Jun 14 '20 at 10:20

If understand the question correctly you want to find a $$k$$-coloring of the given graph, given an ordered list of the vertex such that vertex with the same colors are consecutive in this list.

If that is the case then this problem can be solved greedy.

We should only find maximal independent sets which are contiguous segments in your list starting from the beginning. Start with an empty set. Go for every vertex in the ordered list, if the vertex is not connected to any other node in the set, include it. Otherwise, paint all vertex in the set with the same color, notice they form a consecutive interval in the list, then clear the list and include the current node you are processing. At the end you should paint all nodes remaining in the list with the same color.

## Rationale

We should partition the list in minimum amount of intervals such that all vertex within the same interval are not connected to any other vertex (they are an independent set). Since the first vertex in the list belong to an interval, this interval should start at this vertex. The proposed algorithm will find maximal interval containing this vertex. It is impossible to find any bigger interval containing the first vertex (since the one chosen is maximal) and it doesn't make any sense to find any smaller interval, since not taken vertex will only increase our restrictions in the future while taking next intervals.

## Pseudocode

Graph := Relations between vertex. Graph[u] is the list of all neighbors of u
List := Order of vertex. List[1] = v1, List[2] = v2, etc...

S := {} (Set with all nodes in the interval we are keeping)
color := 0 (Number of colors used so far)

# Iterate through all vertex
for vertex in List:

# Check this node is not connected to any other node in S
ok := True
for neig in Graph[vertex]:
if neig in S:
ok := False
break

if ok:
# If vertex is not neighbor of any other vertex in S, include it in.
else:

# Paint all vertex in S with color
paint(S, color)

# Increase color, since an interval of nodes was painted
color += 1

# Reset S, starting with current node.
S := {vertex}

# Don't forget to paint last interval

# Paint all vertex in S with color
paint(S, color)

# Increase color, since an interval of nodes was painted
color += 1


## Complexity and details

Notice in the implementation you don't need to maintain the set of taken nodes S explicitly, since all nodes in that set belong to an interval they can be easily represented with two pointer (the begin of the interval and the end of the interval). The overall complexity of this solution is $$O(|V| + |E|)$$, since every node is visited once in the first loop, and edges are traversed twice, one per endpoint. Regarding paint function, it is potentially linear in the number of vertex it is painting, but that is ok, since we paint each vertex exactly once.

• First thank you. Do you have an idea how to formal prove the algorithm correctness? I try to assume there is a better solution and contradict it, or induction but I cant manage to finish the proof.. Jun 15 '20 at 14:38
• The overall idea of a formal demonstration is as follows. Given a list $L$ (of nodes in the graph ordered) $\chi(L) \ge \chi(L_{2..n})$. You are taking elements from the beginning of the array, and your only choice here is take less elements than the amount taken by the greedy. But then the remaining array will be larger (has more elements as prefix) so final chromatic number might be only worse. Jun 15 '20 at 19:09