Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [colorings]

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

6
votes
2answers
116 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
64 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
26 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
483 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
26 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
46 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
15 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
124 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
20 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
41 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
41 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
60 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
93 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
29 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
354 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
431 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
32 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. ...
-1
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
224 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
120 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
39 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 ...
3
votes
0answers
429 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
68 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
182 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
44 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
31 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
77 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
107 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
126 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
89 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
329 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
2k 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
222 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
123 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
208 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
406 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
82 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
164 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 ...
3
votes
1answer
460 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
832 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'...
10
votes
2answers
610 views

How to prove that 3-coloring is decidable?

In order to prove that 3-coloring is decidable, is it sufficient to say: Each node in the graph has 3 possible colors Therefore we can enumerate over all $3^n$ possibilities and then check that no ...
1
vote
0answers
64 views

Minimal number of animals in a matching card game [closed]

I saw a card game designed for small children. Each card has a picture of 6 animals on it, and there are 31 cards. When any two cards are compared to each other, they share exactly one animal. The ...
2
votes
0answers
42 views

Edge Covering with different colored edges

I have a graph with the edges already assigned colors and there are edges of the same color as well as different colors incident to each vertex. I would like to find an edge cover (does not have to ...
4
votes
1answer
120 views

Graph Families that are easy to color

What are the non-trivial graph families that have a known chromatic number, or an easy way (polynomial-time algorithm) to compute the latter. Examples would be: Kneser graphs Chordal graphs Do you ...
0
votes
2answers
732 views

Counter example to graph coloring heuristic using BFS

I am considering the following heuristic for the graph coloring problem (i.e. to color a graph $G$ using a minimal number of colors so that no two adjacent vertices have the same color): Explore ...
1
vote
1answer
497 views

How do you produce a CNF from a circular graph with colouring?

If you had a circular graph e.g. A->B->C->D->E->A, and a legal coloring system with 3 colours (e.g. Red, Green Blue), where each node is assigned a colour and no node can be connected to another node ...
1
vote
2answers
256 views

Complexity of 4-coloring a map with constraints

The well-known Four color theorem states that every map which is divided into regions, can be colored using 4 colors such that no two adjacent regions have the same color. In fact, there exists a ...
2
votes
0answers
205 views

Marking nodes of a complete binary tree

Suppose that I have a binary tree with $N = 2^h - 1$ nodes, initially all nodes are unmarked Over time via this process nodes became marked. Suppose that nodes have unique identifiers in range of $[1,...