On the genus of graphs with Lick-White number $k$
HTML articles powered by AMS MathViewer
- by John Mitchem PDF
- Proc. Amer. Math. Soc. 69 (1978), 349-354 Request permission
Abstract:
A graph is called n-degenerate if each of its subgraphs has a vertex of degree at most n. For each n the Lick-White number of graph G is the fewest number of sets into which $V(G)$ can be partitioned such that each set induces an n-degenerate graph. An upper bound is obtained for the Lick-White number of graphs with given clique number. A number of estimates are derived for the number of vertices in triangle-free graphs with prescribed Lick-White number. These results are used to give lower bounds on the genus of such graphs.References
-
B. Bollobás and A. G. Thomason, Uniquely partitionable graphs (to appear).
- O. V. Borodin, The decomposition of graphs into degenerate subgraphs, Diskret. Analiz (1976), 3–11, 78 (Russian). MR 498204 O. V. Borodin and A. V. Kostochka, On an upper bound of the graph’s chromatic number depending on graph’s degree and density, Novosibirsk, Siberia (preprint). P. Catlin, A bound on the chromatic number of graphs (preprint).
- V. Chvátal, The minimality of the Mycielski graph, Graphs and combinatorics (Proc. Capital Conf., George Washington Univ., Washington, D.C., 1973) Lecture Notes in Math., Vol. 406, Springer, Berlin, 1974, pp. 243–246. MR 0360330
- V. Chvátal, The smallest triangle-free $4$-chromatic $4$-regular graph, J. Combinatorial Theory 9 (1970), 93–94. MR 263691, DOI 10.1016/S0021-9800(70)80057-6
- R. J. Cook, Point partition numbers and girth, Proc. Amer. Math. Soc. 49 (1975), 510–514. MR 371734, DOI 10.1090/S0002-9939-1975-0371734-8 B. Descartes, A three-colour problem, Eureka 10 (1948), 24.
- P. Erdős, Graph theory and probability, Canadian J. Math. 11 (1959), 34–38. MR 102081, DOI 10.4153/CJM-1959-003-9 B. Grünbaum, A problem in graph coloring, Amer. Math. Monthly 77 (1970), 1080-1092.
- Frank Harary, Graph theory, Addison-Wesley Publishing Co., Reading, Mass.-Menlo Park, Calif.-London 1969. MR 0256911, DOI 10.21236/AD0705364
- Rhys Price Jones, Hereditary properties and $P$-chromatic numbers, Combinatorics (Proc. British Combinatorial Conf., Univ. Coll. Wales, Aberystwyth, 1973) London Math. Soc. Lecture Note Ser., No. 13, Cambridge Univ. Press, London, 1974, pp. 83–88. MR 0384590
- Hudson V. Kronk, The chromatic number of triangle-free graphs, Graph theory and applications (Proc. Conf., Western Michigan Univ., Kalamazoo, Mich., 1972; dedicated to the memory of J. W. T. Youngs), Lecture Notes in Math., Vol. 303, Springer, Berlin, 1972, pp. 179–181. MR 0335332
- 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
- L. Lovász, On chromatic number of finite set-systems, Acta Math. Acad. Sci. Hungar. 19 (1968), 59–67. MR 220621, DOI 10.1007/BF01894680
- L. Lovász, On decomposition of graphs, Studia Sci. Math. Hungar. 1 (1966), 237–238. MR 202630
- John Mitchem, An extension of Brooks’ theorem to $n$-degenerate graphs, Discrete Math. 17 (1977), no. 3, 291–298. MR 439675, DOI 10.1016/0012-365X(77)90162-5 —, On extremal partitions of graphs, Ph. D. Dissertation, Western Michigan Univ., 1970, pp. 103-109.
- J. Mycielski, Sur le coloriage des graphs, Colloq. Math. 3 (1955), 161–162 (French). MR 69494, DOI 10.4064/cm-3-2-161-162
- J. M. S. Simoes-Pereira, A note on graphs with prescribed clique and point-partition numbers, J. Combinatorial Theory Ser. B 14 (1973), 256–258. MR 314705, DOI 10.1016/0095-8956(73)90008-7
- J. M. S. Simoes-Pereira, Joins of $n$-degenerate graphs and uniquely $(m,n)$-partitionable graphs, J. Combinatorial Theory Ser. B 21 (1976), no. 1, 21–29. MR 419281, DOI 10.1016/0095-8956(76)90023-x —, On graphs uniquely partitionable into n-degenerate subgraphs, Coll. Math. Soc. Janos Bolyai, 10 Infinite and Finite Sets, Keszthely (Hungary), 1973.
- P. Turán, On the theory of graphs, Colloq. Math. 3 (1954), 19–30. MR 62416, DOI 10.4064/cm-3-1-19-30
Additional Information
- © Copyright 1978 American Mathematical Society
- Journal: Proc. Amer. Math. Soc. 69 (1978), 349-354
- MSC: Primary 05C15; Secondary 05C10
- DOI: https://doi.org/10.1090/S0002-9939-1978-0476560-X
- MathSciNet review: 0476560