Chromatic number - Revision history

Vipul at 21:44, 29 May 2012

2012-05-29T21:44:09Z

← Older revision		Revision as of 21:44, 29 May 2012
Line 25:		Line 25:
	\| finite number <math>n</math> \|\| <math>n</math> \|\| The graph is a [[complete graph]]		\| 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]]

Vipul at 19:52, 27 May 2012

2012-05-27T19:52:05Z

← Older revision		Revision as of 19:52, 27 May 2012
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.		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==		==Particular cases==

Vipul: Created page with "{{undirected graph numerical invariant}} ==Definition== The '''chromatic number''' of an undirected graph $G$ is defined as the smallest nonnegative integer <..."

2012-05-27T19:50:04Z

Created page with "{{undirected graph numerical invariant}} ==Definition== The '''chromatic number''' of an undirected graph <math>G</math> is defined as the smallest nonnegative integer <..."

New page

{{undirected graph numerical invariant}}

==Definition==

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>.
==Particular cases==

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

{| class="sortable" border="1"
! 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 <math>n</math> || <math>n</math> || The graph is a [[complete graph]]
|}

Chromatic number - Revision history

Vipul at 21:44, 29 May 2012

Vipul at 19:52, 27 May 2012

Vipul: Created page with "{{undirected graph numerical invariant}} ==Definition== The '''chromatic number''' of an undirected graph G is defined as the smallest nonnegative integer <..."

Vipul: Created page with "{{undirected graph numerical invariant}} ==Definition== The '''chromatic number''' of an undirected graph $G$ is defined as the smallest nonnegative integer <..."