Let $n\in\mathbb{N}$ be a positive integer. Is there a connected graph $G$ such that $G$ cannot be coloured with less than $n$ colours, and every two maximal matchings have non-empty intersection?
(I take maximality with respect to set inclusion.)
$\begingroup$
$\endgroup$
1
asked Sep 16, 2018 at 9:25
-
3$\begingroup$ Do you know any such graph with more than two vertices? $\endgroup$– Fedor PetrovCommented Sep 16, 2018 at 15:00
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
3
Another attempt. Take $K_{n+1} $ and three paths $abc, ade, afg$, $a\in K_{n+1} $, $b, c, d, e, f, g\notin K_{n+1} $. Any maximal matching contains at most one of edges $ab, ad, af$, thus at least two from three edges $bc, de, fg$. Hence any two maximal matchings have a common edge.
answered Sep 16, 2018 at 10:07
-
1$\begingroup$ No, if $K_{2n}=K_4$ has vertices $1, 2, 3, 4$ and you add path $abc$ where $a=1$, the set $\{ab, 23\}$ is a maximal matching that does not contain $bc$. $\endgroup$ Commented Sep 16, 2018 at 10:14
-
$\begingroup$ Ah, you are right, it is maximal by inclusion though not perfect. My bad. $\endgroup$ Commented Sep 16, 2018 at 13:10
-
$\begingroup$ Thanks both Keith and Fedor for your exchange of ideas and then the answer! $\endgroup$ Commented Sep 16, 2018 at 20:24