Chromatic number: Difference between revisions

Latest revision as of 21:44, 29 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

Relation with other invariants

Invariant	Meaning	Relationship
clique number	maximum possible size of a clique, i.e., a subset of the vertex set on which the induced subgraph is a complete graph	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	(independence number) times (chromatic number) $\geq$ size of vertex set

Facts

Self-complementary graph implies chromatic number is at least equal to square root of size of vertex set

@@ 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==
@@ Line 19: / Line 25: @@
 | finite number <math>n</math> || <math>n</math> || The graph is a [[complete graph]]
 |}
+==Relation with other invariants==
+{| class="sortable" border="1"
+! Invariant !! Meaning !! Relationship
+|-
+| [[clique number]] || maximum possible size of a clique, i.e., a subset of the vertex set on which the induced subgraph is a [[complete graph]] || 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 || (independence number) times (chromatic number) <matH>\ge</math> size of vertex set
+|}
+==Facts==
+* [[Self-complementary graph implies chromatic number is at least equal to square root of size of vertex set]]