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 tagged [colorings]

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

0
votes
1answer
20 views

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

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
40 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
14 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
120 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
39 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
58 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
92 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
338 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
389 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
31 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
204 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
116 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
405 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
67 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
171 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
43 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
76 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
104 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
120 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
86 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
282 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
215 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
114 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
183 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
381 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
163 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
442 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
789 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
601 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
693 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
451 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
237 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
198 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
127 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
134 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
103 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 ...