Questions tagged [graph-colouring]
The graph-colouring tag has no usage guidance.
99
questions
39
votes
2answers
944 views
How many distinct colors are needed to lower-bound the choosability of a graph?
A graph is $k$-choosable (also known as $k$-list-colorable) if, for every function $f$ that maps vertices to sets of $k$ colors, there is a color assignment $c$ such that, for all vertices $v$, $c(v)\...
38
votes
17answers
4k views
Conjectures implying Four Color Theorem
Four Color Theorem (4CT) states that every planar graph is four colorable. There are two proofs given by [Appel,Haken 1976] and [Robertson,Sanders,Seymour,Thomas 1997]. Both these proofs are computer-...
37
votes
6answers
3k views
Grid $k$-coloring without monochromatic rectangles
Update: The obstruction set (i.e. the NxM "barrier" between colorable and uncolorable grid sizes) for all monochromatic-rectangle-free 4-colorings is now known.
Anyone feel up to trying 5-colorings? ;...
27
votes
1answer
889 views
Coloring complexity of graphs
Suppose $G$ is a graph with coloring number $d = \chi(G)$. Consider the following game between Alice and Bob. At each round, Alice picks a vertex, and Bob answers with a color in $\{1,\ldots,d-1\}$ ...
26
votes
3answers
953 views
When is relaxed counting hard?
Suppose we relax the problem of counting proper colorings by counting weighted colorings as follows: every proper coloring gets weight 1 and every improper coloring gets weight $c^v$ where $c$ is some ...
23
votes
2answers
829 views
Are shift-chains two-colorable?
For $A\subset [n]$ denote by $a_i$ the $i^{th}$ smallest element of $A$.
For two $k$-element sets, $A,B\subset [n]$, we say that $A\le B$ if $a_i\le b_i$ for every $i$.
A $k$-uniform hypergraph ${\...
21
votes
5answers
3k views
Reasons for which a graph may be not $k$ colorable?
While reasoning a bit on this question, I've tried to identify all the different reasons for which a graph $G = (V_G,E_G)$ may fail to be $k$ colorable. These are the only 2 reasons that I was able to ...
21
votes
2answers
1k views
Coloring Planar Graphs
Consider the set of planar graphs where all the internal faces are triangles. If there is an interior point of odd degree the graph cannot be three colored. If every interior point has even degree can ...
17
votes
3answers
487 views
Is there a constant factor approximation algorithm for 2D rectangle coloring problem?
The problem we consider here is the extension of the well-known interval coloring problem. Instead of intervals we consider rectangles having sides parallel to axes. The objective is to color the ...
17
votes
1answer
940 views
What is the complexity of this edge coloring problem?
Recently, I have encountered the following variant of edge coloring.
Given a connected undirected graph, find a coloring of the edges that uses the maximum number of colors while also satisfying ...
16
votes
1answer
634 views
Why are perfect graphs called perfect?
Sorry, if this is a naive question, but I could not find the justification in any of the major text books like Bondy-Murty, Diestel or West. Perfect graphs have many beautiful properties, but what is ...
16
votes
0answers
433 views
Is graph coloring complete for poly-APX?
Is the graph coloring problem complete for poly-APX under C-reductions
(alternatively, under AP-reductions)? For the graph coloring problem, speaking of a feasible solution means a proper coloring for ...
15
votes
3answers
2k views
Complexity of edge coloring in planar graphs
3-edge coloring of cubic graphs is $NP$-complete. Four Color Theorem is equivalent to "Every cubic planar bridgeless graphs is 3-edge colorable".
What is the complexity of 3-edge coloring of cubic ...
14
votes
0answers
413 views
Question on Products of Graphs
Let $S_{n}(G)$, $C_{n}(G)$, $T_{n}(G)$ be the $n$-fold Strong Product, Cartesian Product and Tensor Product of a graph $G$ on $|V|$ vertices.
Let the chromatic number ($\chi(G)$) and the independence ...
13
votes
4answers
2k views
hardness of approximating the chromatic number in graphs with bounded degree
I am looking for hardness results on vertex coloring of graphs with bounded degree.
Given a graph $G(V,E)$, we know that for any $\epsilon>0$, it's hard to approximate $\chi(G)$ within a factor ...
13
votes
2answers
1k views
Small graph with gap between chromatic and vector chromatic number?
I’m looking for a small graph $G$ whose vector chromatic number is smaller than the chromatic number, $\chi_v(G)<\chi(G)$.
($G$ has vector chromatic number $q$ if there is an assignment $x\colon V ...
12
votes
2answers
540 views
Approximate graph colouring with a promised upper bound on maximum independent set
In my job the following problem arises:
Is there a known algorithm, that approximates the chromatic number of a graph without an independent set of order 65? (So alpha(G)<=64 is known and |V|/64 ...
12
votes
1answer
401 views
Efficient algorithm for near-optimal edge-colourings of hypergraphs
Graph colouring problems are, already, hard enough for most people. Even so, I'm going to have to be difficult and ask a problem about hypergraph colouring.
Question.
What efficient algorithms are ...
12
votes
1answer
753 views
Have these coloring games been solved?
In the paper "On the complexity of some coloring games", Bodlaender gives some open questions about the complexity of deciding if player 1 or 2 has a winning strategy in some graph coloring games. ...
11
votes
3answers
647 views
Graph coloring minimizing the number of colors in every independent set
Is the following claim known?
Claim: For any graph $G$ with $n$ vertices there exists a coloring of $G$ such that every independent set is colored by at most $O(\sqrt{n})$ colors.
11
votes
1answer
253 views
An improper planar coloring with monochromatic component size $\leq 2$
Let us relax the coloring a little bit, that is, we allow a small number of adjacent vertices to be assigned the same color. A monochromatic component is defined to be a connected component in the ...
10
votes
2answers
470 views
Reference Request: Asymptotic hardness of $hk$ coloring $k$-colorable graphs
I heard of a result in approximate graph coloring, but cannot find the source. The result is:
For every constant $h$ there exists a sufficiently large $k$ such that coloring a $k$-colorable graph ...
10
votes
1answer
163 views
Is there a planar 4-regular graph that is 3-acyclic colourable?
A colouring is said to be an acyclic colouring if there is no bicoloured cycle (i.e each cycle gets at least 3 colours).
Burstein proved that 4-regular graphs are 5-acyclic colourable. It seems to me ...
10
votes
1answer
410 views
Hardness of approximating fractional chromatic number on bounded degree graphs
Is it apx-hard to approximate fractional chromatic number on bounded degree graphs?
10
votes
0answers
128 views
Is 4-Coloring restricted to graphs with crossing number 1 NP-complete?
Planar graphs are 4-colorable.
Determining if a planar graph is 3-colorable is NP-Complete.
A graph with a crossing number 1 (graph such that it can be drawn with $\le 1$ crossing) is 5-colorable.
...
9
votes
1answer
303 views
3-coloring planar graphs in $O\left(3^{n^.5}\right)$?
I was wondering if the task of searching for planar 3-colorings is known to be of complexity $O\left(c^{\sqrt{n}}\right)$ or lower? This feels like it would be an intuitive consequence based from ...
9
votes
1answer
223 views
What is known about the hardness of the chromatic index for restricted graph classes?
There is a nice paper from 1991 that contains three diagrams about different graphclass-families showing what is known about the hardness of determining the chromatic index for them.
Are there any ...
8
votes
2answers
355 views
Decision problem related to coloring
Given a $k$-colorable graph $G$ and vertices $u$ and $v$ of $G$, what is the complexity of deciding if every $k$-coloring of $G$ must assign the same color to both $u$ and $v$?
It does not seem ...
8
votes
1answer
188 views
Complexity of graph isomorphism with properly colored edges (ref. request)
An edge-colored graph $G$ is a graph whose edges are labeled with a color (generally represented by an integer). Such a coloring is proper if all adjacent edges in $G$ have different colors. I ...
8
votes
1answer
1k views
How bad can the greedy coloring (list color) for the c-chromatic number of graph be?
c-chromatic number is defined in the paper Partitions of graphs into cographs. It asks for the minimum number of colors used to color vertices such that each color class is a cograph. Cograph is a P4-...
7
votes
3answers
627 views
Hard problems for bounded vertex cover
We know that list coloring problem is W[1]-hard when parameterized by vertex cover. Are there any other problems which are also W[1]-hard parameterized by vertex cover?
7
votes
2answers
735 views
Anti-chromatic number
What is the maximum number of colors that can be used for coloring the vertices of a given graph, with no isolated vertices, such that each vertex should share its color with at least one of its ...
7
votes
1answer
288 views
An image coloring problem
I have a large collection of microscopy images of cell cultures. Each image consists of $10^{10} \times 10^{10}$ pixels. These images have been "segmented", meaning that their pixels have been ...
7
votes
1answer
337 views
Chromatic number of G+v where G is a cograph
Cograph is a well-know graph that does not have induced $P_4$. My questions are about determining the chromatic number of graphs in the class cograph+v.
Notations:
Denote by $\chi(G)$ the chromatic ...
7
votes
1answer
518 views
Razborov's Approximation methods
The approximation mothods is used for deriving lower bounds on the monotone circuit size of k-cliue and perfect matching problem.
People in parameterized complexity theory strongly believe that k-...
7
votes
1answer
305 views
Parallel algorithms to color interval graphs
Several NP-hard graph problems get easy if we consider interval graphs. There is a greedy algorithm to color optimally an interval graph. Just sort the intervals according their left endpoints and ...
7
votes
2answers
293 views
Computing the edge orbits of a graph (and discussing definitions)
A (vertex) automorphism in a graph $G=(V,E)$ is a permutation $\sigma$ of the vertices that preserves adjacency, namely $\sigma(u) \sigma(v) \in E$ if and only if $uv \in E$. The automorphisms of a ...
7
votes
1answer
393 views
The Overfull conjecture in graph theory and $coNP$
I am not good at complexity, but got a possible
relation between a plausible conjecture in graph
theory and $coNP$.
Graph $G$ is Class 1 if it can be edge colored
with $\Delta(G)$ colors, otherwise ...
7
votes
1answer
245 views
3-color a cubic graph such that a MIS receives only two colors
According to Brooks'_theorem, a cubic graph (3-regular graph) containing no $K_4$ can be properly colored by three colors. (Such a color can actually be found in linear time, which is not our primary ...
6
votes
1answer
298 views
NP-hardness of coloring uniform hypergraphs
Since a $2$-uniform hypergraphs are just graphs. The problem of deciding if $2$-uniform is $k$-colorable for $k=1,2$ is easy, and NP-hard for $k \geq 3$ colors. This is well know and I have seen ...
6
votes
2answers
334 views
Hardness of additive approximation to Graph Coloring problem.
In paper Approximation Algorithms for the Chromatic Sum, page 18, authors state that based on the fact that the Graph Coloring problem is hard to approximate with a ratio less than 2 (under the ...
6
votes
1answer
113 views
Existence of certain graph gadget related to coloring odd hole free graph
Crossposted from MO.
Wondering about the existence of graph gadget related to coloring
(or 3-coloring) odd hole free graphs.
Let $G$ be simple $k$-chromatic connected graph with two
vertices $u,v$.
...
6
votes
0answers
89 views
How much is known about coloring of planar graphs with degree bounds?
Are there any references that address the following (open?) questions:
1) Is there an algorithm that 4-colors any planar graph of maximal degree at most 5 in linear time?
2) What is the largest ...
6
votes
0answers
122 views
General Results for Complicated Constraint Satisfaction Problem
Consider the following problem: on a finite two-dimensional grid (say the grid points are vertices of a graph), I need to color the vertices in such a way to satisfy the existence and nonexistence of ...
5
votes
3answers
420 views
Hardness of finding a graph coloring given the optimal number of colors
We know that graph coloring is NP-complete even in some special graph classes. On the other hand if someone tells you the exact value of the chromatic number of the input graph, is this problem ...
5
votes
2answers
4k views
Any relation between the size of maximum independent set and the chromatic number on graph of bounded degree?
Consider an connected undirected graph $G$ with $n$ vertices and maximum degree $\Delta$. Assume $G$ contains a maximum independent set of size $k$. Is there any relation between the chromatic number $...
5
votes
1answer
382 views
Worst case ratio between minimum clique cover and maximum independent set
The maximum independent set problem gives a lower bound for the minimum clique cover problem. This is easy to see because given any clique cover together with an independent set, any two vertices ...
5
votes
1answer
541 views
Chromatic number of planar graph with girth at least k
The four-color theorem claims that, any loopless planar graph is 4-colorable. However, it is NP-Complete to determine the chromatic number of planar graphs, even for those 4-regular ones.
Girth is ...
4
votes
1answer
241 views
Chromatic number of a particular graph
Assume I have a parametrized graph. The parameters are two integers $x$ and $y<x$.
Let $S(x)=\{1, \ldots, x\}$.
The vertices of the graph are all the subsets of $S(x)$ of size $y$. Two vertices ...
4
votes
1answer
10k views
Flood fill vs depth first search
Is the flood fill algorithm the same as depth first search?
If not, how do they differ in complexity?
