According to graphclasses.org, the chromatic number of a subcubic graph can be computed in linear time (because the decision problem COLORABILITY can be solved in linear time). The reference given the website is M. Chlebik and J. Chlebikova, "Approximation hardness of dominating set problems in bounded degree graphs".

Which result of this paper solve the COLORABILITY problem of subcubic graphs in linear time?
The chromatic number of a subcubic graph is 3 unless it is bipartite or $K_4$ is a component by Brook's theorem. Then, why that particular reference is given? Is this simply a case of wrong reference?

Def. A graph with maximum degree at most three is called a subcubic graph.

  • 3
    $\begingroup$ I would think it is simply a wrong reference, some of them are added automatically for example. You can e-mail the people at graphclasses.org and they'll be glad to fix it. $\endgroup$ Sep 16 '20 at 19:48
  • $\begingroup$ @ChristianKomusiewicz Thanks. I think I did it already here. I shall send one more mail just in case. $\endgroup$ Sep 17 '20 at 2:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.