# Tag Info

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

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

9

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

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

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

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

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

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

nice question. Consider the following construction: build k P3s numbered / ordered as 1-2-3 4-5-6 7-8-9, etc. Now 1-2-3 all get colour R by the greedy scheme. Make 4,5,6 all adjacent to 3. Then 4,5,6 each get colour B. Now make vertices 7,8,9 adjacent to 3 and to 6, then they can't get colours R or B. They get Y. Continue with 10-11-12, with 10,11,12 ...

5

What about the following proof? If $\alpha(G) \leq \sqrt{n}$, then the claim holds obviously. Suppose the contrary, and let $I$ be an independent set of $G$ with maximum cardinality $\alpha$. Color $I$ with color 1, and recursively color the graph $G - I$ with colors $2,...,c$. Now, if $K$ is an independent set of $G$, consider $K' = K - I$. By induction ...

5

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. However, it would be very surprising: it would mean that basically, up to encoding, you found a way to always provide a short certificate that a formula is ...

5

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$ contain a $k$-clique? Here is a construction that shows NP-completeness of your problem variant: Let $G$ and $k$ be as in the proof in Garey and Johnson Let $H_1$ ...

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