Chromatic number of graph obtained by removing set of edges from complete graph

555 Views Asked by At

Consider the complete graph on n vertices $S = (V, E)$ and let $K$ be a subset of $E$. If $k$ is the size of the maximal set of independent edges (edges with no common endpoints) in $K$, is the chromatic number of $S-K$ $n - k$?

1

There are 1 best solutions below

1
On BEST ANSWER

Counterexample. Let $n\ge4,$ choose a vertex $v\in V,$ and let $K$ be the set of all edges not incident with $v.$ Then $n-k=\lfloor\frac n2\rfloor+1$ and $\chi(S-K)=2\lt\lfloor\frac n2\rfloor+1=n-k.$

Edit. Even simpler, let $n\ge3$ and $K=E.$