Clique number: Difference between revisions
(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...") |
No edit summary |
||
| 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|| | | [[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 | ||
|} | |} | ||
Revision as of 21:38, 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 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 |
