Point partition numbers and girth

Cook, R. J.

doi:10.1090/S0002-9939-1975-0371734-8

Point partition numbers and girth
HTML articles powered by AMS MathViewer

by R. J. Cook PDF

Proc. Amer. Math. Soc. 49 (1975), 510-514 Request permission

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.

References

R. J. Cook, Chromatic number and girth, Period. Math. Hungar. 6 (1975), 103–107. MR 379257, DOI 10.1007/BF02018401
R. J. Cook, Point-arboricity and girth, J. London Math. Soc. (2) 8 (1974), 322–324. MR 373941, DOI 10.1112/jlms/s2-8.2.322
P. Erdős, Graph theory and probability, Canadian J. Math. 11 (1959), 34–38. MR 102081, DOI 10.4153/CJM-1959-003-9
Frank Harary, Graph theory, Addison-Wesley Publishing Co., Reading, Mass.-Menlo Park, Calif.-London 1969. MR 0256911

Map colour theorem

24

Hudson V. Kronk, An analogue to the Heawood map-colouring problem, J. London Math. Soc. (2) 1 (1969), 750–752. MR 250936, DOI 10.1112/jlms/s2-1.1.750
Don R. Lick and Arthur T. White, $k$-degenerate graphs, Canadian J. Math. 22 (1970), 1082–1096. MR 266812, DOI 10.4153/CJM-1970-125-1
Don R. Lick and Arthur T. White, The point partition numbers of closed $2$-manifolds, J. London Math. Soc. (2) 4 (1972), 577–583. MR 295960, DOI 10.1112/jlms/s2-4.4.577
P. Turán, On the theory of graphs, Colloq. Math. 3 (1954), 19–30. MR 62416, DOI 10.4064/cm-3-1-19-30