Point partition numbers and girth

Author:
R. J. Cook

Journal:
Proc. Amer. Math. Soc. **49** (1975), 510-514

MSC:
Primary 05C99

DOI:
https://doi.org/10.1090/S0002-9939-1975-0371734-8

MathSciNet review:
0371734

Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: In recent papers D. R. Lick and A. T. White have introduced point partition numbers as generalizations of the chromatic number and the point-arboricity of a graph. In particular they proved that an analogue of Heawood's theorem holds for the point partition numbers. In the present paper it is shown that the bounds provided by their result may be improved for graphs of large girth. Finally, using a method of Erdös, it is shown that there exist graphs with large girth and large point-partition number.

**[1]**R. J. Cook,*Chromatic number and girth*, Period. Math. Hungar. (to appear). MR**0379257 (52:163)****[2]**-,*Point-arboricity and girth*, J. London Math. Soc. (2)**8**(1974), 322-324. MR**0373941 (51:10141)****[3]**P. Erdös,*Graph theory and probability*, Canad. J. Math.**11**(1959), 34-38. MR**21**#876. MR**0102081 (21:876)****[4]**F. Harary,*Graph theory*, Addison-Wesley, Reading, Mass., 1969. MR**41**#1566. MR**0256911 (41:1566)****[5]**P. J. Heawood,*Map colour theorem*, Quart. J. Math.**24**(1890), 332-338.**[6]**H. V. Kronk,*An analogue to the Heawood map-colouring problem*, J. London Math. Soc. (2)**1**(1969), 750-752. MR**40**#4167. MR**0250936 (40:4167)****[7]**D. R. Lick and A. T. White,*-degenerate graphs*, Canad. J. Math.**22**(1970), 1082-1096. MR**42**#1715. MR**0266812 (42:1715)****[8]**-,*The point-partition numbers of closed -manifolds*, J. London Math. Soc. (2)**4**(1972), 577-583. MR**45**#5021. MR**0295960 (45:5021)****[9]**P. Turan,*On the theory of graphs*, Colloq. Math.**3**(1954), 19-30. MR**15**, 976. MR**0062416 (15:976b)**

Retrieve articles in *Proceedings of the American Mathematical Society*
with MSC:
05C99

Retrieve articles in all journals with MSC: 05C99

Additional Information

DOI:
https://doi.org/10.1090/S0002-9939-1975-0371734-8

Keywords:
Point partition numbers,
girth,
genus

Article copyright:
© Copyright 1975
American Mathematical Society