Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Do you know of any pretty well known graph parameters which are equal for all small graphs (for $|G|$ small)? That is, there exist two parameters $a(G)$ and $b(G)$ such that $a(G) = b(G)$ for all graphs with $|G|$ at most $k$, where I will require $k$ to be at least 4 to make things somewhat interesting.

I added "pretty well known" to eliminate defining a new graph parameter trivially to make it work, e.g., let $a(G) = \chi(G)$ for all graphs with $|G| \leq 1000$ and let $a(G) = \pi$ for all graphs with $|G| > 1000$.

The more well known the parameters, and the larger the value of $k$, the better the example!

share|improve this question
add comment

1 Answer

$\alpha(G) = \chi(\bar{G})$ for all graphs with $|G| \leq 4$. The first counterexample is the $5$-cycle, and this is the unique counterexample of order $5$. For all orders greater than 5, there are counterexamples. Or, taking the complement of the graphs in both sides gives $\omega(G) = \chi(G)$. These two examples are thus equivalent.

Here, $\alpha(G)$ is the independence number, $\omega(G)$ is the clique number, and $\chi(G)$ is the chromatic number. This, has to do with perfect graphs.

share|improve this answer
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.