<p>According to <a href="https://graphclasses.org/classes/gc_720.html" rel="nofollow noreferrer">graphclasses.org</a>, 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, &quot;<a href="https://www.sciencedirect.com/science/article/pii/S0890540108000928" rel="nofollow noreferrer">Approximation hardness of dominating set problems in bounded degree graphs</a>&quot;.</p>
<p><strong>Which result of this paper solve the COLORABILITY problem of subcubic graphs in linear time?</strong><br />
The chromatic number of a subcubic graph is 3 unless it is bipartite or <span class="math-container">$K_4$</span> is a component by Brook's theorem. Then, why that particular reference is given? Is this simply a case of wrong reference?</p>
<p>Def. A graph with maximum degree at most three is called a <em>subcubic graph</em>.</p>

CC BY-SA 4.0
2020-09-16T19:48:37.647Z
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.
Christian Komusiewicz
CC BY-SA 4.0
2020-09-17T02:57:30.263Z
@ChristianKomusiewicz Thanks. I think I did it already [here](https://graphclasses.org/contact.html). I shall send one more mail just in case.
Cyriac Antony
<graph-colouring>
Computing chromatic number of subcubic graphs
Cyriac Antony
# Computing chromatic number of subcubic graphs

(Asked by: username_0 on 2020-09-16)

According to [graphclasses.org](https://graphclasses.org/classes/gc_720.html), 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](https://www.sciencedirect.com/science/article/pii/S0890540108000928)".

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

**Tags:** graph-colouring

> **Comments:**
> **username_1**: 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.  
> **username_0**: @ChristianKomusiewicz Thanks. I think I did it already [here](https://graphclasses.org/contact.html). I shall send one more mail just in case.  

---

## 0 answers

