# Tag Info

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 ...
• 9,677
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 ...
• 806

### 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, ...
• 29.2k
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
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$...
• 51.1k

### 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

### 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,722

### 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,276

### conversion to DAG

This problem is equivalent to feedback arc set (in a tournament graph). It is NP-hard.
• 1,821
Accepted

• 51.1k

### 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

### 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,429

### 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 ...
• 51.1k

### 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,046

### 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,626

### 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,772
Accepted

• 17.9k
Accepted

### Graph coloring with limit on number of times a color is used

This WALCOM 2022 paper by Bandopadhyay et al. introduces the variant of Coloring (that they refer to as "Budgeted Graph Coloring") that you are looking for! Here is a summary of their ...
• 46
Accepted

### Hardness of Maximum Independent Set in 3-Colorable Graphs

As detailed below, the problem of finding an independent set of size $\Omega(n^{1-\delta})$ in 3-colorable graphs is essentially equivalent to $O(n^\delta)$-approximating 3-COLOR. Currently, the best ...
• 10.8k
I think this question is closely related to the term discrepancy. Here is the defintion. Given a universe $U$ a collection of sets $\mathcal{A}=\{S_i\}$ and a function $\varphi:U\to\{-1,1\}$. For \$S\...