# Questions tagged [colorings]

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

76 questions
Filter by
Sorted by
Tagged with
0answers
42 views

### Determine if a graph has exactly 1 cycle using a SAT solver

I have a connected undirected graph whose edges are either enabled or disabled. I want to create a set of clauses that are SAT iff all enabled edges are part of a single loop. If I assert that each ...
1answer
27 views

### Finding rainbow cycle in digraph colored with $\log n$ colors [closed]

Given a directed graph with $n$ vertices, and $k=\log n$, we are given a coloring of the vertices with $k$ colors. Describe an algorithm determining if there exists a simple cycle in $G$ of ...
0answers
69 views

2answers
214 views

### Is a Knapsack Problem with only Color Constraints NP-Complete?

I have a knapsack problem that has been frustrating me for weeks, in which we consider a set of n items, described by their integer value, and being of one of C colors. There exists a constraint on ...
1answer
57 views

### Showing MAXIMUM CLique is NPO-simple and MAXIMUM GRAPH COLORING is not

Recall the notion of NPO problem. An NPO problem is simple if the following is true: $\forall k \in \mathbb{N}^*. (\forall x. OPT(x) \leq k) \in P$ In words, given any positive integer $k$, the ...
1answer
33 views

### Minimal colouring problem aproximation threshold

Given that 3-colouring and 4-colouring are NP-complete show that the aproximation threshold of the minimal colouring problem is greater or equal than $\frac{4}{3}$. My current approach is to work ...
1answer
92 views

### warm/neutral/cool tone of one image

I wanna determine whether an image belongs to warm/neutral/cool tone. I find Kelvin color temperature to calculate the average temperature of an image over all piexls. But the result seems not good. ...
1answer
79 views

0answers
137 views

### Graph coloring reduction by symmetry

I am trying some methods to solve the graph coloring problem with large data sets. I decided to start off with the total space search but to eliminate certain combinations that are same due to ...
2answers
317 views

### Can one truly build a schedule from graph coloring?

I know that with graph coloring we can build a simple schedule with maybe 9 students and 9 lectures (i.e. these notes) and determine the minimum number of meeting times, but is this feasible in a real ...
1answer
444 views

### Relationship between Coloring a graph and its complement

Let $G = (V, E)$ be a graph and $G^*$ its edge complement (that is, $G^* = (V, E^*)$, where an edge $\{u, v\} \in E^* \Leftrightarrow \{u, v\} \not \in E$). What is the relationship between a ...
1answer
85 views

### Label coloring to maximize number of “balanced” triangles (NP-hardness)

Define a triangle in undirected graph $G$ is balanced if the edge labels in the triangle are $(+1, +1, +1)$, $(-1, -1, +1)$, $(+1, -1, -1)$ or $(-1, +1, -1)$ (social balance theory). Problem ...
0answers
178 views

### How to color sudoku with this added constraint?

I couldn't figure out an algorithm for following graph coloring problem: Output color of each vertex for this graph: Given a solved 9*9 sudoku board that is a 9-colored board, applied first three ...
1answer
538 views

### Euler graph k-coloring (np-completeness proof)

I've been studying np-completeness proofs by reduction, and was wondering whether my approach to the following problem is viable. Define an Euler graph as a graph that 1) is connected, and 2) has ...
2answers
979 views

### Showing that 3-colorable is NP-complete

Just as a background, 3-colorable problem is as follows: Given a graph $G = (V, E)$, is it possible to color the vertices using just 3 colors such that no neighboring vertices have the same color? I'...