Clique number - Revision history

Vipul at 21:40, 29 May 2012

2012-05-29T21:40:08Z

@@ 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
 |}

Vipul at 21:38, 29 May 2012

2012-05-29T21:38:37Z

← Older revision		Revision as of 21:38, 29 May 2012
Line 10:		Line 10:
	! Invariant !! Meaning !! Relationship		! 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 <math>\le</math> ~~Chromatic~~ number. Note that for any [[bipartite graph]] with at least one edge, the two numbers are both equal to 2.		\| [[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 <math>\le</math> 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 of a graph\|complement]]<br>independence number = clique number of complement		\| [[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
	\|}		\|}

Vipul: Created page with "{{undirected graph numerical invariant}} ==Definition== The '''clique number''' of an undirected graph is defined as the maximum possible size of a clique in the gra..."

2012-05-29T21:38:20Z

Created page with "{{undirected graph numerical invariant}} ==Definition== The '''clique number''' of an undirected graph is defined as the maximum possible size of a clique in the gra..."

New page

{{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==

{| class="sortable" border="1"
! 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 <math>\le</math> 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 of a graph|complement]]<br>independence number = clique number of complement
|}