Stack Exchange Network

Stack Exchange network consists of 174 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 on graph coloring, an assignment of colors to elements of a graph subject to specific constraints.

-1
votes
0answers
36 views

Proving minimum graph coloring is NP-hard [closed]

The problem is the following: A vertex coloring is an assignment of labels or colors to each vertex of a graph such that no edge connects two identically colored vertices. A vertex coloring that ...
-1
votes
2answers
37 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
38 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
56 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
88 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
27 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
36 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
323 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
309 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
30 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
45 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
163 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
76 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
38 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
360 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
58 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
155 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
42 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
30 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
73 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
82 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
111 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
80 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 ...
3
votes
1answer
240 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
204 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
106 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
140 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
352 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
158 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
357 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
567 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
575 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
39 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
620 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
378 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
197 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
194 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,...
-1
votes
1answer
126 views

All but Five Three Colorable

An NP Problem Named All But Five Three Colorable(AB53C) is defined as follows :- Input : Connected Graph G(V,E) The Connected Graph is AB53C, iff the Given Graph is 3-Colorable by leaving UPTO 5 ...
5
votes
1answer
130 views

Finding $k$ claws ($K_{1,3}$ bipartite graphs) in a graph?

Usually questions deal with claw-free graphs, but suppose we are given a graph $G$ and there are $k$ vertex-disjoing claws in the graph, how can we derive a randomised algorithm using color coding to ...
1
vote
1answer
1k views

3-Coloring Problem Question [duplicate]

So I understand that finding a solution to the 3-coloring problem takes exponential time. However, say you had a friend who you could give a graph G to and he can say in constant time whether it is 3-...
0
votes
2answers
96 views

Does 2-edge-colourability imply 2-colourability?

Why is it that if the edges of an undirected graph G can be grouped into two sets such that every vertex is incident to at most 1 edge from each set, then the graph is 2-colorable. The reason that I ...
1
vote
1answer
37 views

Why do Benes networks form bipartite graphs when you build a constraint graph for them?

I was learning about Benes networks and was wondering why they formed bipartite graphs (and thus are two colorable) when one draws a constraint graph for them. The constraint graph is based on the ...
9
votes
1answer
113 views

What is the name of the problem? (partitioning graph into three covers)

I was wondering if this problem has a name: Given a simple graph whose edges are colored red, blue and green, $G=(V,B\cup R\cup G)$, is there a vertex-coloring $c:V\to \{B,R,G\}$ such that every edge ...
-2
votes
1answer
703 views

How to figure out the minimal number of colors needed to color specific given graphs?

I found this question on the net and I'm wondering what is the process for answering such questions? I assume there is some formula that works for all graphs? 1.a. Consider the undirected graph with ...
7
votes
3answers
7k views

Application of the four color theorem

I was reading up on the four color theorem and am wondering if there is any practical application of it. (I dont think seperating the map into four different colors can be considered an application.) ...