Skip to main content
Source Link

Matching number and chromatic number

If $G$ is a (finite) graph, denote with $\mu(G)$ the size of any maximum matching in $G$ (this number is also called the "matching number" of $G$).

For odd integers $n$ we have $n=\chi(K_n) = 2\cdot\mu(K_n) + 1$. Question: is there a non-complete graph $G$ with $\chi(G) = 2\cdot\mu(G) + 1$?