Chromatic number: Difference between revisions

Revision as of 19:52, 27 May 2012

Template:Undirected graph numerical invariant

Definition

The chromatic number of an undirected graph $G$ is defined as the smallest nonnegative integer $c$ such that the vertex set of $G$ can be partitioned into $c$ disjoint subsets such that the induced subgraph on each subset is the empty subset. In other words, there are no edges between vertices in the same subset.

We often say that $G$ is:

$c$ -colorable if the chromatic number of $G$ is less than or equal to $c$ .
$c$ -chromatic if the chromatic number of $G$ is equal to $c$ .

The chromatic number of $G$ is denoted either $\gamma (G)$ or $\chi (G)$ . The latter notation is sometimes used for the Euler characteristic, which is a different graph invariant.

Particular cases

We consider the case of a graph on a non-empty vertex set.

Number of vertices	Chromatic number	Conclusion
any	1	The graph is an empty graph
any	2	The graph is a non-empty bipartite graph
finite number $n$	$n$	The graph is a complete graph

@@ Line 5: / Line 5: @@
 The '''chromatic number''' of an [[undirected graph]] <math>G</math> is defined as the smallest nonnegative integer <math>c</math> such that the vertex set of <math>G</math> can be partitioned into <math>c</math> disjoint subsets such that the [[induced subgraph]] on each subset is the [[empty subset]]. In other words, there are no edges between vertices in the same subset.
-We often say that <matH>G</math> is <math>c</math>-chromatic if the chromatic number is less than or equal to <math>c</math>.
+We often say that <math>G</math> is:
+* <math>c</math>-colorable if the chromatic number of <math>G</math> is less than or equal to <math>c</math>.
+* <math>c</math>-chromatic if the chromatic number of <math>G</math> is equal to <math>c</math>.
+The chromatic number of <math>G</math> is denoted either <math>\gamma(G)</math> or <math>\chi(G)</math>. The latter notation is sometimes used for the [[Euler characteristic of a graph|Euler characteristic]], which is a different graph invariant.
 ==Particular cases==