Zentralblatt MATH

Publications of (and about) Paul Erdös

Zbl.No:  791.05038
Autor:  Erdös, Paul; Gimbel, John
Title:  Some problems and results in cochromatic theory. (In English)
Source:  Gimbel, John (ed.) et al., Quo vadis, graph theory? A source book for challenges and directions. Amsterdam: North-Holland, Ann. Discrete Math. 55, 261-264 (1993).
Review:  Given a graph G, the cochromatic number z(G) of G is the fewest number of parts into which V(G) must be partitioned so that each part induces in G either an empty or complete graph. The authors survey some of the most interesting open questions involving cochromatic numbers. For example, let z(n) denote the maximum cochromatic number among all graphs with order n. Then it can be shown that z(n) = \Theta({n \over ln n}). However, even for some small values of n (e.g. n = 12), the exact value of z(n) is unknown. This paper includes open questions relating the cochromatic number and size, genus, chromatic number and clique number.
Reviewer:  L.Lesniak Foster (Madison)
Classif.:  * 05C15 Chromatic theory of graphs and maps
                   00A07 Problem books
Keywords:  cochromatic number; complete graph

© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag

Books Problems Set Theory Combinatorics Extremal Probl/Ramsey Th.
Graph Theory Add.Number Theory Mult.Number Theory Analysis Geometry
Probabability Personalia About Paul Erdös Publication Year Home Page