Find (if there exists) a graph $G$ such that $X'(G)=5$ and $X(G)=6$. If there is no such a graph then explain why.

204 Views Asked by At

Find (if there exists) a graph $G$ such that $X'(G)=5$ and $X(G)=6$. If there is no such a graph then explain why.

So we know the following things

$[1]$ $X(G) \leq \Delta(G)+1$ or $X(G) \leq \Delta(G)$ if graph is connected and is neither a complete graph nor an odd cycle

$[2]$ $\Delta(G) \leq X'(G) \leq \Delta(G)+1$

So knowing the mentioned above properties we can state that there should exist such a graph and it should have $\Delta(G) = 5$ and it should be connected and complete or connected and an odd cycle, am I right?

1

There are 1 best solutions below

6
On BEST ANSWER

Strictly speaking, what you've argued is that if such a graph exists, it would need to have $\Delta(G)=5$, and if it's connected, it would have to be an odd cycle or a complete graph. (Given a connected example, we could always make a nonconnected example by, say, throwing in some extra isolated vertices.) On its own this doesn't tell you that such a graph does exist, but it suggest that there are only a few candidates that you need to look at -- and one of the obvious candidates does in fact turn out to work.