Vertex colouring and forbidden subgraphs -- a survey (Q1889838): Difference between revisions
From MaRDI portal
Set profile property. |
Set OpenAlex properties. |
||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2089191641 / rank | |||
Normal rank |
Latest revision as of 20:02, 19 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Vertex colouring and forbidden subgraphs -- a survey |
scientific article |
Statements
Vertex colouring and forbidden subgraphs -- a survey (English)
0 references
13 December 2004
0 references
The monograph ``Graph coloring problems'' by \textit{T. R. Jensen} and \textit{B. Toft} (Wiley, New York) (1995; Zbl 0855.05054) provides a comprehensive list of unsolved problems in chromatic graph theory. The present survey gives an account of the recent development in the area. It focusses in the recent solution of Berge's strong perfect graph conjecture proved by Chudnovsky, Robertson, Seymour and Thomas, and some related unsolved problems. Then the authors consider the more general problem of finding an upper bound for the chromatic number as a function of the clique number. One such problem is the conjecture of B. Reed that the chromatic number is always bounded above by \((\omega+ \Delta)/2\) where \(\omega\) is the clique number, and \(\Delta\) is the maximum degree. The authors also discuss upper bounds on the chromatic number in graphs where specific subgraphs are excluded. The survey contains many unsolved problems and references.
0 references
strong perfect graph conjecture
0 references
chromatic number
0 references
clique number
0 references