Math 2.0

Combinatorics Definition

Clique number

Builds on Clique

Definition

Let GG be a finite graph. The clique number ω(G)\omega(G) is the largest number of vertices of a clique in GG.

Remarks

The vertices of a clique need different colours. Thus ω(G)≤χ(G)\omega(G) \le \chi(G), where χ(G)\chi(G) is the chromatic number. For the complete graph, ω(Kn)=n\omega(K_n) = n. For the cycle graph CnC_n with n≥4n \ge 4, ω(Cn)=2\omega(C_n) = 2. The inequality ω(G)≤χ(G)\omega(G) \le \chi(G) can be strict: for C5C_5, ω=2\omega = 2 and χ=3\chi = 3.

Reading path

To understand this page from the ground up, read these 2 pages in order. The foundations come first.

Show the path as a graph
Clique, definition, no evidence levelCliquedefinitionClique number, definition, no evidence levelClique numberdefinition
Each page uses the pages above it. The colour of the bar on a box shows how strong the evidence is, and the box also gives it as text. The list has the same pages.
  • no evidence level
  1. Clique definition
  2. Clique number definition

Where this leads

1 page builds on this one.

Further reading

  1. Web https://en.wikipedia.org/wiki/Clique_(graph_theory), Definitions
About this page
Tag0WCKRBHFFD
URIm2://0WCKRBHFFD
Kinddefinition
WritingW1 stated
MSC05C69
DefinesClique number
UsesClique

Markdown · JSON · Edit on GitHub

What this page needs for W2

  • edge instance_of in: one example (0 of 1)
  • edge not_instance_of in: one non-example that fails one clause (0 of 1)

The writing levels say how complete the text of a page is. They do not measure its truth.

What links here

Used by