Questions tagged [colorings]

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

Filter by
Sorted by
Tagged with
3
votes
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 ...
1
vote
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 ...
2
votes
0answers
69 views

Proving NP-completeness of an extension in List Coloring Problem

In the List Coloring Problem (LCP), one is given an undirected graph $G(V,E)$, each vertex $v \in V$ is given a list of permissible colors $L(v) \subseteq \{1,2,\dots,k\}$, we want to find a coloring $...
1
vote
2answers
37 views

What is a polynomial-time algorithm for determining whether two trees, with colored nodes, are isomorphic or not

Provide any polynomial-time algorithm (even a large degree polynomial) which determines whether two rooted colored trees are isomorphic to each-other or not. For example, consider the following two ...
1
vote
0answers
11 views

complexity of computing fractional edge-chromatic number of an edge-weighted graph

Let $(G,w)$ be an edge-weighted graph, where the weights $w(e)$ are assumed to be rational. My question is: What is the complexity of computing $\chi'_f(G,w)$, the fractional edge-chromatic number of ...
3
votes
2answers
53 views

Connection between max independent set and graph coloring

Is there any connection between the size of the largest independent set in a graph, and the minimum number of colors required to color the graph? I know that we can potentially color all the vertices ...
-1
votes
1answer
30 views

3-Coloring Graph problem

Can we prove that the 3 coloring graph problem (where no two adjacent nodes have same color) is NP instead of NP-complete? $$\mathrm{3COLOR} = \{\langle G \rangle \mid G \text{ is colorable with 3 ...
4
votes
4answers
264 views

Algorithms for 2-colouring a 2 x N matrix

Our task is to color a given $2 \times N$ matrix with two colours red (R) and blue (B) such that no two adjacent cells are blue. For red, there are no restrictions. An example of all possible ...
6
votes
2answers
127 views

Find a $\log_2(|V|)$ long cycle where each node is of different color

Here's a question from an algorithms exam by Prof. Noga Alon that I just can't wrap my head around. Let $G=(V,E)$ be a directed graph where $|V|=n$. Let $k=\lfloor \log_2(n)\rfloor$. Each node in ...
4
votes
2answers
89 views

How to create RGB-colors with equal vector norm?

I am trying to do the following: Interprete RGB color values as a 3-D vektor Transform the RGB color into polar coordinates L, teta and phi Create colors with constant L The math behind this is the ...
1
vote
0answers
30 views

Optimal improper vertex-coloring of graph with weighted edges

I have an undirected graph with weighted edges. I want to color the vertices with a given $k$ colors. Let's assume there is no proper coloring with $k$ colors such that adjacent nodes will always have ...
2
votes
2answers
494 views

Easy instances of the coloring problem on graphs with degree at most 4

Given a graph with some set of colors, the goal of the coloring problem is to color the input graph with as few number of colors as possible, such that no adjacent vertices have the same color. In ...
1
vote
1answer
34 views

Shortest path in graph by flipping binary colored nodes to one color [closed]

Given a graph consists of two-colored nodes(e.g. white and black) and a starting node, and every time you visit a node, its color is switched(from black to white, or, white to black), how to find the ...
1
vote
1answer
54 views

Reducing a graph without changing its chromatic number

Does reducing a graph (removing or replacing vertices or edges) without changing its chromatic number has a specific name? Take this cactus graph as an example (although my question is about an ...
1
vote
0answers
18 views

Relation between deficiency and color class parity of graphs

Let $G$ be a graph with total vertices $|V(G)|$. Let the maximum degree of the graph be $\Delta$. Let us assume the graph is total colourable( no adjacent vertices, adjacent edges and an edge and its ...
1
vote
1answer
235 views

How to reduce 3-COLOR to 42-COLOR?

The requirement is that two adjacent vertices have different colors, and max. 42 colors. I show that $ \text{42-COLOR} $ is in NP and then I must reduce it from $ \text{3-COLOR} $. Here it becomes ...
1
vote
1answer
22 views

Color a graph using k colors, k>4, with the most equal distribution of colors

Given a planar graph G with $N$ nodes, 4 colors are enough to color each node, so that adjacent nodes have different colors. Let $k > 4$. Is there an algorithm to color the nodes with $k$ colors, ...
-1
votes
2answers
43 views

Graph Coloring Problem

Can solutions to the graph coloring problem be used in the prison system to keep known enemies apart with the goal of reducing violence?
3
votes
1answer
42 views

Coloring grid with flexible number of colors and flexible number of occurrence per color

Suppose we have an $m \times n$ grid or table, with $m$ being the number of rows and $n$ being the number of columns. The user can select the number of colors (let's say $k$ colors) and how often each ...
5
votes
1answer
72 views

Complexity of a graph parity-coloring problem

Suppose I have a positively weighted (bounded-degree) graph $G$ where each vertex in $G$ is colored either black or white. I'm curious about the complexity of the following problem: Find a subset $S$...
4
votes
1answer
95 views

Equivalent Colorings of Graphs

Call two proper graph colorings equivalent if one can be obtained from the other by a permutation of the colors. In other words, they are the "same" coloring. I'm interested in finding proper non-...
-1
votes
1answer
33 views

Adding edges to a graph that satisfy logical expressions

Easy question. I have a homework problem with its answer that i am unable to interpret. An explanation on how to arrive at the answer is what I'm looking for. Please let me know what the palette ...
1
vote
1answer
39 views

Counting $k$-Colorings $\mathcal{O}(\phi^{n + m})$ Solution

Given an undirected graph $G = (V, E)$ with $n$ vertices and $m$ edges, how many $k$-colorings of $G$ exist? A $k$-coloring is a function $c: V \to \{ 1, 2, \dots, k \}$ such that $c(u) \neq c(v)$ for ...
3
votes
1answer
401 views

An efficient algorithm to decide if a triangulation is 3-colourable

I don't know how to start with the following exercise: Design an efficient algorithm to decide whether a given triangulation with $n $ points is $3$-colourable. The triangulation is given by a ...
4
votes
1answer
641 views

Algorithms for solving Flow game

Lately I've been toying with an automatic solver for the Android/iPhone game Flow. In this game, you start with several pairs of squares on a grid, and you have to connect each pair, without crossing ...
1
vote
1answer
33 views

Highly colored vertices in greedy coloring imply existence of subtrees

I have a graph $G$ on which I try greedy coloring; i.e. I order the vertices and then start coloring them according to their order and I assign each vertex the smallest possible color available to it. ...
0
votes
1answer
46 views

Colouring the graph

We have a directed simple graph $G$. Out-degree of any vertex is at most $k$ in $G$. We need to show that $G$ is $2k+1$-partite.
0
votes
1answer
297 views

#3-Coloring Problem for Tree with Some Pre-Colored Nodes [closed]

I have a undirected tree and three colors to choose from. Some nodes are already colored; these nodes and their colors are given. What is an efficient algorithm to find the number of ways to color the ...
1
vote
1answer
220 views

Graph coloring decision problem NP-complete

Given a graph $G = (V, E)$ and a natural number $k$, consider the problem of determining whether there is a way to color the vertices with two colors in such a way that at least $k$ edges are ...
1
vote
1answer
42 views

Graph Coloring Problem : How to Think About Algorithms Exer 1.6.2

The problem says: Given an undirected simple graph G such that each node has at most d + 1 neighbors, color each node with one of d + 1 colors so that for each edge the two nodes have different ...
2
votes
0answers
461 views

Graph Coloring Real World Applications

I'd like to know whether recent graph coloring algorithms that one can find nicely listed here have found it's place in real world applications or are they just simply pushing boundaries in this ...
0
votes
0answers
75 views

I/O-Efficient graph coloring

I have an undirected Graph $G$, which is stored in the form of an adjacency list in external memory. I'm looking for an I/O efficient algorithm which computes a valid coloring for $G$ with at most $...
1
vote
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 ...
-1
votes
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 ...
0
votes
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 ...
2
votes
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. ...
0
votes
1answer
79 views

Find hamming codewords in r=2^k dimensions

There is the original problem, and an equivalent problem. The equivalent problem: construct a set $A$ that contains bit arrays of length $r-1$, where $|A|=2^{r-1}/r$ and $hamming \space distance (i, ...
1
vote
0answers
123 views

Hard vertex 3-coloring for easily edge-colorable graph

Suppose we want to use a reduction of 3-colorability to a certain problem to prove said problem is NP-c. But to pull off the reduction, one needs to take a graph-class for which 3-coloring is NP-c and ...
1
vote
0answers
137 views

Edge coloring optimization using dynamic programming

The problem is to find an algorithm that colors all the edges in any arbitrary tree T with a root r, let's say in blue and red, such that the number of blue edges is maximal and there isn't more than ...
2
votes
1answer
95 views

How may an algorithm always color optimally connected bipartite graphs?

Let's consider a greedy algorithm for the coloration problem called the Dsatur algorithm, designed by Daniel Brélaz in 1979 at the EPFL, Switzerland.. This algorithm is based on an order of vertices ...
4
votes
1answer
477 views

Is every acyclic graph 2-colorable?

Every acyclic graph can be transformed structurally to a tree. Therefore, every node on odd numbered levels can be colored with color $X$ and every node on even numbered levels can be colored with ...
3
votes
1answer
3k views

Is Graph 2-Coloring NP-Complete?

I know there is a polynomial time algorithm for 2-coloring. But should the answer be "No" or should it be "Maybe"? Since 2-coloring is in NP and we dont know if there is a reduction of any NP-complete ...
0
votes
0answers
239 views

Using symmetry to prune DFS tree for graph coloring problem

I am working on the graph coloring problem. I came up with the following. Let $S^L$ be the set of all colorings with $N$ colors for a graph with $L$ nodes. This is shorthand notation for $\{1, 2, 3, ....
0
votes
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 ...
1
vote
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 ...
1
vote
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 ...
1
vote
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 ...
2
votes
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 ...
2
votes
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 ...
0
votes
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'...