2
$\begingroup$

As we all know it is $NPH$ to check whether $G=(V,E)$ is $k$-colorable or not. It is also hard to find the chromatic number of $G$. But I'd like to ask what are some good (or best known) approximation for coloring a general graph?

More formally, I am looking at a graph $G=(V,E)$ for which I do not know the chromatic number. I am trying to find a good coloring of such a graph. What is considered good?

For example, if $d=d(G)$ is the degeneracy of the graph, I can color $G$ in $d+1$ colors in linear time. The degeneracy can be computed in polynomial (linear) time.

I'd like to ask for other (polynomial) coloring algorithms that do not know the chromatic number of the graph (Yet, they are may attempt to approximate it in polynomial time), which (obviously) won't lead to $\chi(G)$ colors, but might lead me to either:

  • $f(\chi(G))$-coloring, better if $f$ is linear, but also if not.
  • $g(G)$-coloring, where $g$ is a parameter of the graph $G$. Such as: degeneracy, maximal degree, etc. Prefferably better than $d+1$-coloring.

Basically, I have a graph that I only know $V$ and $E$. I don't know $\chi(G)$ or anything else. So anything I want to know must be computed (or approximatex) polynomially.

Now, I want to color this graph in the best possible way that will require polynomial time. Or, in one of the best ways if there are several.

I tried looking online, but could not find such results. There are many negative results, showing some approximations are $NPH$, but I am looking for the positive results.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

Dinur, Mossel and Regev showed in their paper Conditional hardness for approximate coloring that assuming some variant of the 2-to-1 conjecture (a reduction of the same family as the more famous unique games conjecture), for every $C>4$ it is NP-hard to distinguish between 4-colorable graphs and $C$-colorable graphs. (The recently proved variant of the 2-to-1 conjecture doesn't suffice for their result, since it lacks perfect completeness.) In particular, assuming P≠NP, this implies that there is no polynomial time algorithm that colors a 4-colorable graph with any constant number of colors.

There are various extensions of this result. For example, under a stronger assumption, the same paper shows that you can consider 3-colorable graphs instead of 4-colorable graphs. Follow-up works give similar results in which $C$ is a growing function of the number of vertices, as well as similar results for hypergraphs without assuming any known conjectures (other than the implicit P≠NP), and unconditional results for graphs in which the coloring needs to be legal only for almost all vertices. Another genre of related results shows that it is NP-hard to distinguish $a$-colorable graphs from $b$-colorable graphs, where $b$ is a fast growing function of $a$ (see for example Wrochna and Živný, which get $b$ exponential in $a$).

The best known positive result in this direction is due to Kawarabayshi and Thorup, who give an efficient algorithm that colors a 3-colorable graph using $O(n^{0.19996})$ colors.

Improve this answer
$\endgroup$
9
  • $\begingroup$ I see. However, most of the resukts mentioned are on the negative side. Are there not positive polynomial approximations? I have seen some papers which tackle how to approximate a coloring for a graph known to be $3$-colored, yet hardly found any approximations for a general graph (Even if the approximations are bad, I'm trying to find a grasp of what is known to be solved polynomially). $\endgroup$
    – Marik S.
    Oct 13, 2021 at 11:49
  • $\begingroup$ Any approximation algorithm that works for general graphs will also work for 3-colorable graphs. $\endgroup$
    – Yuval Filmus
    Oct 13, 2021 at 12:03
  • $\begingroup$ Yes, but so far I found only approximations for $3$ coloring. Not for the general graph. $\endgroup$
    – Marik S.
    Oct 13, 2021 at 12:13
  • $\begingroup$ The classic algorithm of Wigderson colors a $k$-colorable graph using $2k \lceil n^{1-1/(k-1)} \rceil$ colors. $\endgroup$
    – Yuval Filmus
    Oct 13, 2021 at 12:17
  • $\begingroup$ Perhaps I need to edit my question to clarify, but my intention is in a general graph, in which $k=\chi(G)$ is unknown to me, are there any approximation algorithms? Or if there are some ways to approximate $k$, I can use what you suggested. $\endgroup$
    – Marik S.
    Oct 13, 2021 at 12:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.