16
votes
Accepted
Is the 3-coloring problem NP-hard on graphs of maximal degree 3?
The answer is no: the 3-coloring problem can be solved in linear time on graphs of maximal degree 3 or less, by application of Brooks' theorem. I wasted some time figuring this out, so I thought I'd ...
- 8,786
13
votes
Accepted
Is there a planar 4-regular graph that is 3-acyclic colourable?
I can prove that no 4-regular graphs are 3-acyclic colorable.
Consider a 4-regular graph with a 3-coloring. If we call the colors $a, b, c$, then one of the three subgraphs generated by restricting ...
- 764
13
votes
Accepted
NP-hardness of coloring uniform hypergraphs
$2$-coloring $s$-uniform hypergraphs is also called Set Splitting, problem [SP4] in Garey-Johnson book.
The hardness proof is due to Lovasz in this paper.
- 4,828
10
votes
What is the complexity of the fastest method of k-coloring any graph?
There are non-obvious improvements over simple brute-force search for $k$-coloring (and for many other NP-hard problems). The obvious approach would take roughly $k^n$ time, but one can do it in time $...
- 4,624
9
votes
Accepted
3-coloring planar graphs in $O\left(3^{n^.5}\right)$?
I recommend reading Sections 7 and 14 in the excellent book by Cygan, Fomin, Kowalik, Lokshtanov, Marx, Pilipczuk, Pilipczuk, and Saurabh.
In short, Gu and Tamaki give a quadratic time algorithm ...
- 2,247
9
votes
When should one start looking at existing results in theoretical CS?
Scenario 1: You spend several months tinkering around with colorings, not reading any literature. After many failed attempts you finally discover one that works. Before you can write a paper about it, ...
- 28.1k
8
votes
How many distinct colors are needed to lower-bound the choosability of a graph?
As a bit of unashamed self-promotion, Marthe Bonamy and I found more negative answers. In particular, Theorem 4 of http://arxiv.org/abs/1507.03495 improves upon the aforementioned result of Král' and ...
- 1,952
7
votes
Accepted
On the coloring number of small graphs with small cliques
Uniformly random $k^2$-vertex graphs have clique size $O(\log k)$, well under $k$, and independent set size also $O(\log k)$, implying that their chromatic number is $\Omega(k^2/\log k)$.
As for $k^2$...
- 50.8k
7
votes
Have these coloring games been solved?
The answer is yes, for the first game you list! This result was only established in 2019. Here is a link to the paper: Costa et al. 2019
Even more recently, some variants of the first game were proved ...
- 71
7
votes
Canonical way of coloring graphs (individualization) for isomorphism purpose
Typically the way individualization goes is this. You're trying to decide if two vertex-colored graphs $G$ and $H$ are isomorphic in a way that respects the colors (sends vertices of color $c$ in $G$ ...
- 36.7k
7
votes
Accepted
Partition into triangles in a 3-partite graphe
A recent paper by Custic, Klinz, Woeginger "Geometric versions of the three-dimensional assignment problem under general norms", Discrete Optimization 18: 38-55 (2015) contains (and proves) the ...
- 5,762
7
votes
Hard problems for bounded vertex cover
$(k,r)$-center is another (arguably natural) problem that is $W[1]$-hard parameterized by vertex cover. (See a recent preprint by Katsikarelis, me, and Paschos here - sorry about the self-promotion!). ...
- 3,256
6
votes
conversion to DAG
This problem is equivalent to feedback arc set (in a tournament graph). It is NP-hard.
- 1,682
6
votes
Hard problems for bounded vertex cover
Here is a problem (with lists!) which is known to be W[1]-hard parameterized by Vertex Cover (indeed, even by the number of vertices in the input graph). The problem is known as the "Arc Supply" ...
- 3,256
6
votes
Accepted
Is the difference between the acyclic chromatic number and the star chromatic number unbounded?
While I know nothing about these measures, quick googling led me to the paper
Michael O. Albertson, Glenn G. Chappell, H. A. Kierstead, André Kündgen, Radhika Ramamurthi: Coloring with no $2$-colored $...
- 16.5k
5
votes
Accepted
Computing the edge orbits of a graph (and discussing definitions)
It turns out that yes, indeed, there are two possible definitions for edge-automorphisms... but it turns out that they almost always coincide so that it seems that people often get away with not ...
- 3,382
5
votes
Complexity of graph isomorphism with properly colored edges (ref. request)
In general, if the number of adjacent edges, which have the same color, is bounded by a constant, say d. Then, the isomorphism problem for n-vertex graphs can be solved in n^(cd) for some constant c. ...
- 51
5
votes
Deciding $\omega(G)>k$ when $\alpha(G)$ and $\chi(G)$ have bounds and are known
The NP-hardness proof for CLIQUE in the book by Garey and Johnson shows that the following problem is NP-complete:
Instance: An integer $k$; a $k$-partite graph $G=(V,E)$
Question: Does $G$ ...
- 5,762
5
votes
Accepted
Complexity of relaxed edge colouring
If $G$ is $2k$-regular, then a relaxed edge coloring with exactly $k$ colors is the same thing as a 2-factorization, and is known to always exist by results of Petersen 1891.
Otherwise, let $k=\lceil\...
- 50.8k
4
votes
Hard problems for bounded vertex cover
I don't know if there is any pure graph theoretic problem which is hard in bounded vertex cover, and if there is any it is very interesting for me to see such problem. However, here is a problem of ...
- 3,440
4
votes
3-color a cubic graph such that a MIS receives only two colors
It at least doesn't work out that for every maximum independent set there is a 3-coloring of the graph which 2-colors the independent set. Here is a counterexample to that stronger version of your ...
- 1,419
4
votes
Accepted
Existence of certain graph gadget related to coloring odd hole free graph
One can extract an argument that this cannot work from the paper found by OP in the MO thread. Suppose $G=(V,E)$ is as required, and $c:V\to[k]$ is a $k$-coloring. By the assumption, $c(u)\neq c(v)$. ...
- 2,490
4
votes
Does distance-2 coloring fit in Telle and Proskurowski 's algorithm for partial-k trees?
distance-2 coloring is coloring in the square (d(x,y) <= 2 implies xy an edge in the square). If a graph has tw k, its square has bounded clique-width (see Gurski-Wanke and Suchan-Todinca). See Oum ...
- 1,036
4
votes
Producing colouring of maximal planar graphs G from colouring of dual of G
The simple but useless answer is that I don't know of such a scheme. However, more to the point: proving that such a scheme worked would be tantamount to proving the 4-color theorem. It is very easy ...
- 50.8k
4
votes
Coloring intersection graph of squares
Even computing a maximum independent set of unit axis-parallel squares is known to be np-hard:
https://www.sciencedirect.com/science/article/pii/0020019081901113?via%3Dihub
Since coloring is a "...
- 9,596
4
votes
Graph classes where giving a q-clique edge cover makes testing for q-colouring easy
Let $G=(V,E)$ be an arbitrary instance of $3$-coloring.
Construct a new graph $G'=(V',E')$ as follows:
$V'$ contains all the vertices in $V$, and for every edge $e\in E$ it contains a corresponding ...
- 5,762
4
votes
Accepted
Complexity of maximum k-edge-colorable subgraph of a bipartite graph
A bipartite multigraph is $k$-edge colorable iff the maximum degree of any vertex is at most $k$. So we are asking for a subgraph $H=(V,F)$ of a given bipartite graph $G=(V,E)$ such that $\delta_H(v) \...
- 6,979
3
votes
Coloring where all colors are present in closed neighborhood of every vertex
I would call this a polychromatic coloring of the closed neighborhood hypergraph.
I don't think this has been studied before for general graphs.
Here is a paper studying the question when edges are ...
- 14k
3
votes
Accepted
3-colourability of Eulerian maximal planar graph
When you make deductions in this coloring problem you are following paths in the dual graph to the triangulation. Any inconsistency could be described by a cycle in the dual graph (a cycle of ...
- 50.8k
Only top scored, non community-wiki answers of a minimum length are eligible