2
$\begingroup$

If you remove any $2$ vertices from a complete graph, the chromatic number gets decreased by two. (The famous double-critical graph conjecture is about the existence of a non-complete graph such that any $2$ connected vertices can be removed such that the chromatic number of the graph decreases by $2$.)

Now there is a kind of graph where you can pick some $2$ points and get the chromatic number decreased. Let $C_{2n+1}$ for $n>2$ be the "circle" graph on $2n+1$ points, and add a "top" point $t$ to it, and connect $t$ to every other point. The chromatic number of that graph is $4$. If you remove $t$ and some other point, then the chromatic number of the resulting graph is $2$. The question is if you can construct a similar example without having to resort to a "top node" $t$ as above, which is connected to everything else. More formally:

Question. Given a positive integer $n\in\mathbb{N}$, is there a connected graph $G = (V,E)$ with $\chi(G) \geq n$, having the following properties?

  1. For every $v\in V$ there is $w\in V\setminus \{v\}$ such that $\{v,w\}\notin E$, and
  2. there are $v\neq w\in V$ such that $\chi(G\setminus\{v,w\}) = \chi(G)-2$.
$\endgroup$
6
  • $\begingroup$ Take any bipartite graph that has a 4-cycle. Add the two diagonals to make a 4-clique. Then the chromatic number is 4 but you can bring it down to 2 by removing two vertices. $\endgroup$ Commented Feb 2, 2021 at 10:28
  • $\begingroup$ OK cool - you want to post it as an answer? Otherwise I'll remove my question $\endgroup$ Commented Feb 2, 2021 at 10:32
  • $\begingroup$ Maybe you can think of a deeper version? $\endgroup$ Commented Feb 2, 2021 at 10:36
  • $\begingroup$ Yes, maybe. Meanwhile, I'll remove the question. - Thanks again for your example! $\endgroup$ Commented Feb 2, 2021 at 11:33
  • $\begingroup$ @bof Yes, I only claimed to answer it for $n=4$. $\endgroup$ Commented Feb 3, 2021 at 6:25

1 Answer 1

1
$\begingroup$

Let $G_0=(V_0,E_0)$ be a complete graph of order $n\ge4$. Choose two distinct points $a,b\in V_0$ and two distinct points $x,y\notin V_0$. The graph $G=(V,E)$ with vertex set $V=V_0\cup\{x,y\}$ and edge set $E=E_0\cup\{\{a,x\},\{b,y\}\}$ satisfies your requirements with $\chi(G)=n$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .