0
$\begingroup$

A graph I mean an undirected one. A complete subgraph of a graph $G$ is called a clique. A maximal clique is a clique which is maximal with respect to inclusion. The clique number of $G$, written as $\omega (G)$, is the maximum size of a clique in $G$. Clearly, a finite graph has finite clique number. But my question is that:

What properties imply that an infinite graph $G$ have a finite clique number?

$\endgroup$

closed as off-topic by Claude Leibovici, José Carlos Santos, Parcly Taxel, muaddib, Sahiba Arora Jan 30 '18 at 13:05

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "This question is missing context or other details: Please improve the question by providing additional context, which ideally includes your thoughts on the problem and any attempts you have made to solve it. This information helps others identify where you have difficulties and helps them write answers appropriate to your experience level." – Claude Leibovici, José Carlos Santos, Parcly Taxel, muaddib, Sahiba Arora
If this question can be reworded to fit the rules in the help center, please edit the question.

1
$\begingroup$

A graph has finite clique number if there exists some number $n$ such that for any $n$ vertices in the graph, at least two of them are not joined by an edge.

Therefore any graph with finite degree $d$ has finite clique number, less than or equal to $d+1$.

More generally, if the degree is infinite but for any integer $n$ larger than some bound $d$ there are less than $n$ vertices with degree $n-1$ or higher, then the clique number is finite and at most $d$.

$\endgroup$
  • $\begingroup$ Thank you so much for your answer. Are these conditions sufficient or not? $\endgroup$ – M.Ramana Jan 30 '18 at 11:33
  • $\begingroup$ Surely they are sufficient, but they are definitely not necessary. $\endgroup$ – Arnaud Mortier Jan 30 '18 at 11:34

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