0
$\begingroup$

Let $G= (V, E)$ be a simple graph satisfy the following:

  • Independence number is $3$,
  • Clique number is $\frac{n^2}{4}$,
  • Number of vertices is $n^2$, where $n$ is even.

Let $f \in$ End$(G)$, where End$(G)$ is the collection of all homomorphism from $G$ to $G$.

I want to show that atmost three clique of maximum size can be mapped under $f$ to a single clique of maximum size.

Since independence number of a graph is $3$ so that atmost three vertices can be mapped into a single single vertex. Also, it is easy to verified that image of maximal clique is a maximal clique under a homomorphism. I am stuck here, how to prove that atmost three clique of maximum size can be mapped to a single clique of maximum size.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.