Suppose $G, H$ are finite, simple, undirected graphs and there is a bijection between the vertex sets $\varphi:V(G) \to V(H)$ such that for all $v\in V$ we have $$\text{deg}_G(v) = \deg_H(\varphi(v)).$$
Does this imply that $\chi(G) = \chi(H)$?
$\begingroup$
$\endgroup$
2
asked Mar 29, 2016 at 6:40
-
$\begingroup$ In other words, $G,H$ have the same degree sequence. $\endgroup$– Nate EldredgeMar 29, 2016 at 6:58
-
2$\begingroup$ Play with the Petersen graph. Its edges have no three coloring. Now `untwist' it. $\endgroup$– Wilberd van der KallenMar 29, 2016 at 7:01
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
4
Let $G$ be a 6-cycle and let $H$ be two 3-cycles.
Or, if you want them connected, let $G$ be a 6-cycle with an extra edge between vertices 1 and 3, and $H$ a 6-cycle with an extra edge between vertices 1 and 4.
answered Mar 29, 2016 at 6:57
-
$\begingroup$ One can even make this example connected - add a "diameter" edge to $G$ and an edge connecting two triangles to $H$. $\endgroup$– WojowuMar 29, 2016 at 7:01
-
2$\begingroup$ Isn't simpler argument all $k$-regular graphs would have the same chromatic number? $\endgroup$– joroMar 29, 2016 at 7:38
-
2$\begingroup$ Well, all $k$-regular graphs of a given order. $\endgroup$– verretMar 29, 2016 at 7:44
-
1$\begingroup$ @joro: I figured that if the OP knew that not all $k$-regular graphs of a given order had the same chromatic number, he wouldn't have asked the question. So I didn't think just quoting the fact would be helpful, and thus I gave an explicit example instead. (Incidentally, my first example consists of two 2-regular graphs of order 6.) $\endgroup$ Mar 29, 2016 at 13:40
$\begingroup$
$\endgroup$
1
There is also a general principle one can apply: If you have any parameter $\alpha$ of graphs so that there is an efficient (polynomial-time) algorithm to compute $\alpha (G)$, then it is extremely implausible that $\alpha$ determines the chromatic number since this would imply that $P=NP$. (It is known that computing the chromatic number is $NP$-hard.)
answered Sep 13, 2019 at 9:39
-
$\begingroup$ Could't it still be that it is NP complete to determine whether a degree sequence is, say, "three colorable"? $\endgroup$ Sep 13, 2019 at 18:23