TransWikia.com

Computing chromatic number of subcubic graphs

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.

Add your own answers!

Ask a Question

Get help from others!

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP