Bounds for the chromatic number of graphs with partial information (Q1869218)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 1896002
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | Bounds for the chromatic number of graphs with partial information |
scientific article; zbMATH DE number 1896002 |
Statements
Bounds for the chromatic number of graphs with partial information (English)
0 references
9 April 2003
0 references
Bounds for the chromatic number, clique number, and independence number of a graph \(G\) are obtained in terms of the number of vertices and edges of \(G\), and in terms of \(G\)'s degree sequence. The tightness of these bounds, which include several known bounds but also a new upper bound for the chromatic number, is examined and the structure of extreme examples attaining the bounds are given.
0 references
chromatic number
0 references
clique number
0 references
independence number
0 references
degree sequence
0 references
0.9233792
0 references
0.9071399
0 references
0.90694076
0 references
0.9053848
0 references
0.9011924
0 references
0.8998313
0 references
