Clique number: Difference between revisions

Latest revision as of 21:40, 29 May 2012

Template:Undirected graph numerical invariant

Definition

The clique number of an undirected graph is defined as the maximum possible size of a clique in the graph. Here, a clique is a subset of the vertex set such that the induced subgraph on that subset is a complete graph.

Relation with other invariants

Invariant	Meaning	Relationship
chromatic number	minimum possible number of pieces into which the vertex set needs to be subdivided so that there are no edges within any piece	clique number $\leq$ chromatic number. Note that for any bipartite graph with at least one edge, the two numbers are both equal to 2.
independence number	maximum possible size of an independent subset of the vertex set, i.e., a subset such that there are no edges between vertices in that subset	clique number = independence number of complement independence number = clique number of complement

Relation with graph properties

Clique number	Graph property
1	The graph is an edgeless graph, i.e., it has no edges
2	The graph has at least one edge, and is a triangle-free graph
$n$ where $n$ is the finite size of the vertex set	The graph is a complete graph

@@ Line 13: / Line 13: @@
 |-
 | [[independence number]] || maximum possible size of an independent subset of the vertex set, i.e., a subset such that there are no edges between vertices in that subset || clique number = independence number of [[complement of a graph|complement]]<br>independence number = clique number of complement
+|}
+==Relation with graph properties==
+{| class="sortable" border="1"
+! Clique number !! Graph property
+|-
+| 1 || The graph is an [[edgeless graph]], i.e., it has no edges
+|-
+| 2 || The graph has at least one edge, and is a [[triangle-free graph]]
+|-
+| <math>n</matH> where <math>n</math> is the finite size of the vertex set || The graph is a [[complete graph]]
 |}