15

This problem is NP-hard and APX-hard; see: Adamaszek and Popa, Approximation and Hardness Results for the Maximum Edge $q$-coloring Problem, Lecture Notes in Computer Science 6507 (2010) 132-143. The parameterized complexity aspects of this problem is addressed in this recent paper.


14

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 is at least the antichromatic number. In the other direction, take any maximal matching, and color each of the pairs using a different color. Every other vertex ...


13

$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.


13

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 to either $a$ and $b$ colored vertices, $a$ and $c$ vcertices, or $b$ and $c$ vertices must have as many edges as vertices. But all graphs with as many edges as ...


12

In the paper Absolute Planar Retracts and the Four Color Conjecture, Pavol Hell proved several equivalente formulations for the 4CT. One of them reads as follows: Every planar graph is 4-colorable (The 4CT) iff there exists an absolute planar retract. (A subgraph $H$ of a graph $G$ is a retract of $G$ if there exists a homomorphism $r: V(G)\to V(H)$ ...


11

There are much stronger results for approximate graph coloring. S. Khot, Improved inapproximability results for maxclique, chromatic number and approximate graph coloring. show that for all sufficiently large constants $k$ it is NP-hard to color a $k$-colorable graph with $k^{\Omega(log k)}$ colors A very recent result of S. Huang Improved Hardness of ...


11

Here are the references: S. Khanna, N. Linial, and S. Safra, On the hardness of approximating the chromatic number, Combinatoria, 20 (2000), pp. 393–415. C. Lund and M. Yannakakis, On the hardness of approximating minimization problems, J. ACM, 41 (1994), pp. 960–981.


11

The following claim is known to me, but may not count because it is unpublished: Any graph on $n$ vertices can be colored so that any induced subgraph $H$ of chromatic number at most $k$ uses at most $\chi(H)+B$ colors, where $B(B+1)\leq 2kn$. This is a proof by induction; the motivation was to consider colorings which use few colors not only on the graph ...


10

Not quite what you ask for, but here's a lower bound - a graph for which any coloring will result in an independent set colored by $\sqrt{n}$ colors: Take $\sqrt{n}$ copies of $K_{\sqrt{n}}$, and connect all vertices to a single vertex $s$. Obviously, every set of $\sqrt{n}$ vertices from different $K$'s is independent, and in every copy of $K_{\sqrt{n}}$ ...


10

As David pointed out, Khot's paper, "Improved Inapproximability Results for MaxClique, Chromatic Number and Approximate Graph Coloring", Theorem 1.6, says it is NP-hard to color $K$-colorable graph with $2^{\Omega((\log K)^2)}$ colors for graphs with degree at most $2^{2^{(\log K)^2}}$, for sufficiently large constant $K$. In other words, for graphs of ...


9

There is an inapproximability result for coloring bounded degree graphs in Khot's FOCS'01 paper, "Improved Inapproximability Results for MaxClique, Chromatic Number and Approximate Graph Coloring" — it's probably weaker than you want, but at least it's in the right direction. He proves that, for a parameter $k$ (assumed to be constant), and for $k$-...


9

The Lovász $\vartheta$ function is an efficiently computable function with the property $$ \alpha(G) \leq \vartheta(G) \leq \bar{\chi}(G), $$ where $\alpha$ is independence number and $\bar{\chi}$ is clique cover number. If the bound $\frac{\bar{\chi}(G)}{\alpha(G)} \leq n^{1-\varepsilon}$ were true for some constant $\varepsilon > 0$, then we would have ...


9

Add the edge $(u,v)$. Your property holds if and only if $G$ is no longer $k$-colorable.


9

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 $O(2^n \cdot poly(n))$, and for $k = 3$, one can get $O(1.33^n)$. Algorithms in this area involve simple but interesting applications of dynamic programming ...


8

The Flood Fill algorithm is a particular case of the Depth First Seach algorithm, on regular mesh graphs: Wikipedia indicates that they do not work on the same kind of data: The Flood Fill algorithm is "an algorithm that determines the area connected to a given node in a multi-dimensional array." The Depth First Seach algorithm is "an algorithm for ...


8

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 Sgall in certain cases. The examples we use are complete bipartite graphs, where we used some extremal combinatorics to analyse them. The work was motivated in ...


8

The best known hardness of approximating the chromatic number of $3$-colorable graphs with bounded maximum degree is due to Venkatesan Guruswami and Sanjeev Khanna, On the Hardness of 4-Coloring a 3-Colorable Graph: There is a constant $\Delta$ such that given a $3$-colorable graph with maximum degree at most $\Delta$, it is NP-hard to color it using ...


8

I think Artem is on the right track with perfection: As cographs are $P_4$-free, cograph+v is $C_5$-free (and $C_{2k+1}$-free and $\overline{C}_{2k+1}$-free, $k>1$) and so they are perfect graphs. This means the only thing that is pushing the chromatic number up is clique size. So if $\chi(G+v) = \chi(G) + 1$, it is because v has increased the maximum ...


8

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 which finds a branch-decomposition of a planar graph of width at most $3\sqrt{n}$. Then Robertson and Seymour in (5.1) give a tree-decomposition of width less than ...


7

This paper: http://www.mimuw.edu.pl/~kowalik/papers/grotzsch-full.pdf gives an $O(n\log{n})$-time 3-colouring algorithm for triangle-free planar graphs, improving on Thomassen's $O(n^2)$-time constructive proof. I'm not exactly sure, but does this answer your question?


7

I make my comment an answer. If we don't require that $\chi_v(G)$ is an integer then the smallest example is $G=C_5$ (a cycle on 5 vertices): $$\chi_v(C_5) = \sqrt{5} < 3 = \chi(C_5) . \qquad\text{[Lovász]}$$ It's not hard to transform this example to an example where $\chi_v(G)$ is integer. Let $G_1$ be a union of two 5-cycles $C_5^{(1)}$ and $C_5^{(2)}$...


7

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 to be PSPACE-complete. This result can be found here: Marcilon et al. 2019.


7

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$ to those of the same color $c$ in $H$). You pick a vertex $v$ in $G$ and assign it a new color, say $c$, that has not been used before. This is called "...


7

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 following proposition: Proposition 5.1: Partition into triangles on 6-regular tripartite graphs is NP-complete. Now just follow the reduction in the proof with a ...


7

$(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!). The problem here is to select $k$ vertices (centers) so that all other vertices are at distance at most $r$ from the closest center. This generalizes $k$-...


7

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$-vertex triangle-free graphs, their chromatic number can be $\Theta(k/\sqrt{\log k})$ (and not higher); see Kim, Jeong Han (1995), "The Ramsey number $R(3,t)$ ...


6

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" problem, and it was proved W[1]-hard (parameterized by the number of vertices) by Bodlaender, myself and Penninkx, even on planar graphs. Input is a simple directed ...


6

This problem is equivalent to feedback arc set (in a tournament graph). It is NP-hard.


6

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\Delta/2\rceil$ where $\Delta$ is the maximum degree of $G$. Then obviously, at least $k$ colors are needed in any relaxed coloring of $G$. But $G$ can be ...


5

This result might be helpful: Emden-Weinert, Hougardy, and Kreuter proved that determining whether a graph with maximum degree $\Delta$ has a coloring using $ k=$$\Delta - \sqrt\Delta +1 $ colors is NP-complete ($k\ge 3$) T. Emden-Weinert, S. Hougardy, B. Kreuter, Uniquely colourable graphs and the hardness of colouring graphs of large girth, Combin. ...


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