1
$\begingroup$

Given a graph $G$, how can we generate all possible color vectors that could be generated via greedy coloring?

N.B. Greedy coloring takes a graph and an order of vertices. It traverses vertices following that order and, while visiting a vertex $v$, puts the minimum color absent in all neighbors of $v$.

If $G$ has $n$ vertices, there are $n!$ possible orders. But by applying greedy coloring on all those $n!$ orders, obtained set of color vectors may be very small. Ex: Consider $n$ isolated vertices. Only one color vector $(1,1,\cdots, 1)$ is possible.

I am looking for an efficient solution to identify those color vectors.

$\endgroup$
3
  • $\begingroup$ One way is to consider all $n!$ orders and run greedy coloring. But I am asking for $O(\zeta)$ algorithms where $\zeta$ number of such coloring. $\endgroup$ Mar 21, 2023 at 18:22
  • $\begingroup$ I don't understand what you are asking. What does 'greedy coloring' mean? Please include context and background in your question to make it understandable and interesting for others. Don't use comments for clarifications; include all information in your question. If your post consists of just a single sentence, you probably need to add more context, motivation, background, and explanation of what approaches you've already tried and rejected and why. $\endgroup$
    – D.W.
    Mar 22, 2023 at 16:48
  • $\begingroup$ @D.W. I have added the total information regarding the question. $\endgroup$ Mar 28, 2023 at 23:39

1 Answer 1

2
$\begingroup$

Let $V_i := \{ u \mid c_u = i \}$ to denote the color classes of a proper coloring $c$. Let $V_{\leq i} := \bigcup_{j \leq i} V_j$ to denote the union of the first $i$ color classes.

The coloring can be generated by a greedy coloring if and only if $V_{\leq i}$ is maximal for all $i$, meaning that there is no new vertex $v \in V \setminus V_{\leq i}$ that can be recolored as $i$ while still maintaining a proper coloring.

Proof:

  • ($\implies$): Suppose for contradiction that there exists a vertex $v \in V \setminus V_{\leq i}$ that can be recolored as $i$. During greedy coloring, the smaller color $i$ could have been used for $v$, contradicting the how greedy coloring works.
  • ($\impliedby$): Order the vertices in $V_1$ first, those in $V_2$ next, and so on. We show that greedy coloring on this order will produce coloring $c$. Consider a vertex $u$ such that $c_u = i$. Because $V_i$ is an independent set, we can use the color $i$. Any smaller color $j < i$ is already used by a neighbor of $u$, since otherwise we could recolor $u$ to $j$, contradicting the assumption that $V_{\leq i}$ is maximal.

By using the characterization, we can design a recursive enumeration algorithm. To enumerate all greedy colorings of vertices $V$, first enumerate all maximal independent sets. An independent set will be a color class $V_i$. For each independent set $V_i$, the algorithm recurses for the graph with $V_i$ removed. Pseudocode:

def enumrate(V, C = []):
  if V = ∅ then:
    yield C
    return
  for each maximal independent set I in G[V]:
    enumerate(V - I, C + [I])

There is an output-sensitive maximal independent set enumeration algorithm that runs in $O(VE)$ time per output (see Listing all maximal cliques - Wikipedia). Using that subroutine, the enumeration algorithm is output-sensitive because the recursion depth is bounded and any leaf node yields one solution. I'm uncertain whether the runtime per output can be further optimized.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.