Last call to make your voice heard! Our 2022 Developer Survey closes in less than a week. Take survey.
14 votes
Accepted

Anti-chromatic number

Your problem is equivalent to maximum matching. In an optimal coloring, each color class is connected. Choosing one edge from each color class, we get a matching. This shows that the maximum matching ...
user avatar
  • 14.1k
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.
user avatar
  • 4,828
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 ...
user avatar
  • 732
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 ...
user avatar
9 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 $...
user avatar
  • 4,584
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, ...
user avatar
  • 26.4k
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 ...
user avatar
  • 1,952
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 ...
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 ...
user avatar
  • 5,712
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$ ...
user avatar
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!). ...
user avatar
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$...
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" ...
user avatar
  • 3,216
6 votes

conversion to DAG

This problem is equivalent to feedback arc set (in a tournament graph). It is NP-hard.
user avatar
  • 1,423
6 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\...
user avatar
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 $...
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 ...
user avatar
  • 3,381
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$ ...
user avatar
  • 5,712
5 votes
Accepted

The Overfull conjecture in graph theory and $coNP$

For the possible reduction you are mentioning, if you find such a reduction from SAT to this particular edge-coloring problem, and additionnally you assume OC, then it would indeed mean NP $=$ co-NP. ...
user avatar
  • 7,643
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. ...
user avatar
4 votes
Accepted

For which graph classes the fractional chromatic index rounded up equals the chromatic index?

It is known that for any multigraph $G$ on at most 8 vertices, $\chi'(G)$ is the maximum of the maximum degree and the ceiling of the odd-sets bound, see http://dx.doi.org/10.1016/S0012-365X(96)00364-...
user avatar
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)$. ...
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 ...
user avatar
  • 3,420
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 ...
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 ...
user avatar
  • 1,026
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 ...
user avatar
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 "...
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 ...
user avatar
  • 5,712
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....
user avatar
  • 46

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