17 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 ...
a3nm's user avatar
  • 8,896
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 ...
isaacg's user avatar
  • 776
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.
vb le's user avatar
  • 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 $...
Andy Drucker's user avatar
  • 4,634
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 ...
Alex Golovnev's user avatar
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, ...
Andrej Bauer's user avatar
  • 28.3k
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$...
David Eppstein's user avatar
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$ ...
Joshua Grochow's user avatar
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 ...
Grapher's user avatar
  • 71
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 ...
Gamow's user avatar
  • 5,772
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!). ...
Michael Lampis's user avatar
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" ...
daniello's user avatar
  • 3,256
6 votes

conversion to DAG

This problem is equivalent to feedback arc set (in a tournament graph). It is NP-hard.
Laakeri's user avatar
  • 1,767
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 $...
Emil Jeřábek's user avatar
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 ...
mhum's user avatar
  • 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. ...
user55611's user avatar
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$ ...
Gamow's user avatar
  • 5,772
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\...
David Eppstein's user avatar
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 ...
Andrew Morgan's user avatar
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 ...
Saeed's user avatar
  • 3,440
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 ...
David Eppstein's user avatar
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 ...
M. kanté's user avatar
  • 1,046
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 "...
Sariel Har-Peled's user avatar
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 ...
Gamow's user avatar
  • 5,772
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) \...
Chandra Chekuri's user avatar
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 ...
domotorp's user avatar
  • 13.9k
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 ...
David Eppstein's user avatar
3 votes
Accepted

3-coloring graph zero-knowledge proof

Yes, it would still be zero knowledge. However, it wouldn't be a proof of anything, since whether the colors matched or not, you still know nothing about whether the graph is actually 3-colored or not....
David's user avatar
  • 46
3 votes
Accepted

Name of this graph partitioning problem? (related to coloring)

(Copied from a comment:) If you are not interested in approximations, then you can equally well look at the question of maximizing the number of edges between different parts, and this is usually ...
Jukka Suomela's user avatar
3 votes
Accepted

Graph labelling where vertices with a common neighbour get different labels

`Special labelling' is not exactly $L(0,1)$-coloring, but is very close. In $L(0,1)$-coloring, neighboring vertices can get the same colour even if they have a common neighbor. Speciall labelling do ...
Cyriac Antony's user avatar

Only top scored, non community-wiki answers of a minimum length are eligible