# Questions tagged [colorings]

Questions on graph coloring, an assignment of colors to elements of a graph subject to specific constraints.

146 questions
Filter by
Sorted by
Tagged with
1 vote
41 views

### Reducing the Independent Set Problem to Independent Set for 3-Colorable Graphs

I am exploring a reduction from the general Independent Set Problem to the Independent Set Problem specifically for 3-colorable graphs. The goal is to demonstrate that the maximal independent set of a ...
46 views

### Algorithm for 3-coloring a graph, given a search algorithm that finds a k-colored graph for $k \ge 4$ if one exists, and otherwise returns false

The problem statement is: Given a search algorithm that finds and returns a k-colored graph for $k \ge 4$ if one exists, and otherwise returns false, show that there exists a search algorithm for 3-...
677 views

### Is 2-coloring in NL or L?

The 2-coloring problem is in P. How can I prove that it is in NL or L? I see that I should create a deterministic/nondeterministic algorithm with logarithmic space, but I have no idea how to store ...
• 83
77 views

### Proof that the K coloring problem is weakly or strong NP-complete?

As far as I know, the K coloring problem is NP-complete. However, I'm a bit confused about how to determine whether a problem is weakly or strongly NP-complete. If an NP-complete problem is decidable ...
• 21
1 vote
116 views

### NP-hardness of modified distance-colouring of graphs

Given a graph $G =(V,E)$, a set of colors $\mathcal{C}=\{0,1,2,3,...,c-1\}$, and an integer $r$, I want to know if I can find a coloring procedure that can assign a color to each nodes (all nodes must ...
• 11
30 views

### Why is there no self-stabilizing determinsitic algorithm for vertex coloring in general graphs?

This question considers the design of a deterministic self-stabilizing algorithm for vertex coloring in uniform anonymous networks. Uniform anonymous networks do not have distinguished nodes and all ...
• 171
46 views

### Let 3-COL-$K_4$-FREE be the decision problem that asks if a graph that doesn't contain $K_4$ admits a 3-coloring. Show that the problem is NP-complete

I'm kind of struggling with this excercise. The obvious thing to try is to show that 3-COL $\leq_p$ 3-COL-$K_4$-FREE ($\leq_p$ stands for polynomial reduction). It is clear that 3-COL-$K_4$-FREE is in ...
1 vote
27 views

### Color a a general graph with maximal degree $\Delta$ using $2^{O(\Delta)}$ colors within $\log^{*}n$ rounds

Consider the following algorithm $A$ to 6-color an rooted tree within $\log^{*}n$ rounds in a distributed system: 1: Assume that initially the nodes have IDs of size $\log(n)$ bits 2: The root is ...
• 325
29 views

### How to calculate transition areas of biomes in an image

I'm generating biomes for my game and I would like to store them in a single RGB image like the one below. A color hue can then be mapped to an ID through a table lookup. The problem I face is that I ...
• 101
1 vote
55 views

### How to generate all possible colour vectors generated by greedy colouring on a graph?

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 ...
25 views

• 807
1 vote
534 views

### What algorithm will visit each node in a graph a number of times equal to the number of paths to that node from the root?

First Few Iterations of the Algorithm We have an algorithm in which a squirrel visits the nodes of a directed graph. Our graph has two colors of edges: black and white. Initially, the graph has black ...