Questions tagged [colorings]
Questions on graph coloring, an assignment of colors to elements of a graph subject to specific constraints.
11
questions
8
votes
3
answers
13k
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.)
...
- 639
23
votes
5
answers
5k
views
Assuming P = NP, how would one solve the graph coloring problem in polynomial time?
Assuming we have $\sf P = NP$, how would I show how to solve the graph coloring problem in polynomial time?
Given a graph $G = (V,E)$, find a valid coloring $\chi(G) : V \to \{1,2,\cdots,k\}$ for ...
- 352
7
votes
5
answers
462
views
How to edge-color a directed acyclic graph so that every path visits none or all edges of each color?
Given a directed acyclic graph $G$ and a start vertex $s$ and an end vertex $e$, consider a coloring of the edges valid if, for every path from $s$ to $e$ and every color $c$, either $c$ is never ...
- 73
5
votes
1
answer
604
views
A variation of the graph coloring problem
Given a set of colors $M$ and a graph $G=(V,E)$. Allocate the colors to minimize the number edges with same color on the two vertices of the edge (i.e. minimize pairs of adjoining vertices with same ...
- 502
4
votes
1
answer
1k
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 ...
- 233
4
votes
1
answer
2k
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 ...
- 43
4
votes
1
answer
118
views
What is a guarenteed amount of colors, depending on the graph's arboricity
Let $G=(V,E)$ and denote $d=d(G)$ its maximal degree and $a=a(G)$ its arboricity. My question is: what is the smallest amount of colors $f(a)$, such that a $f(a)$-coloring is guarenteed to exist?
For ...
- 445
3
votes
1
answer
765
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 ...
- 457
3
votes
1
answer
63
views
Using the chromatic number to compute an optimal coloring
Suppose we are given a graph $G$ of order $n$ and a black box that can efficiently (polynomial time) compute the chromatic number $\chi(G)$. I am curious to hear how would one go about in order to ...
- 2,450
1
vote
1
answer
145
views
Time complexity for FPT algorithm
I'm studying the issue of FPT algorithms and came to the k-disjoint triangles problem as can be seen
here on slide 60.
The problem summary is given a graph G and variable k, are there k disjoint ...
- 25
1
vote
1
answer
429
views
How to find the lightest path that has at least one vertex of each color?
I've faced this question in my homework.
In a graph $G=(V,\ E)$ where every $v\in V$ has a color, a colored path is a path such that it has at least one vertex of each color.
We're given a directed ...
- 449