Zentralblatt MATH
Publications of (and about) Paul Erdös
Zbl.No: 501.05033
Autor: Erdös, Paul; Hajnal, András; Szemeredi, E.
Title: On almost bipartite large chromatic graphs. (In English)
Source: Ann. Discrete Math. 12, 117-123 (1982).
Review: What can be said about the set of all finite subgraphs of a graph G when it is known that its chromatic number \chi(G) is greater than \kappa, a given finite or infinite cardinal? For finite \kappa, there are finite graphs G without any short circuits, but for infinite \kappa, G has to contain all finite bipartite graphs. This result from 1966 is here extended in various ways. For instance, bounds are given for the chromatic numbers of the finite subgraphs of G when special restrictions are imposed on G. Some open problems are also given.
Reviewer: O.Frank
Classif.: * 05C15 Chromatic theory of graphs and maps
Keywords: subgraphs of large graphs; chromatic number; finite bipartite graphs
© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag