Theoretical Computer Science Asked by Cyriac Antony on January 13, 2021
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.
Get help from others!
Recent Answers
Recent Questions
© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP