Remote Access Proceedings of the American Mathematical Society
Green Open Access

Proceedings of the American Mathematical Society

ISSN 1088-6826(online) ISSN 0002-9939(print)

 

 

On the genus of graphs with Lick-White number $ k$


Author: John Mitchem
Journal: Proc. Amer. Math. Soc. 69 (1978), 349-354
MSC: Primary 05C15; Secondary 05C10
MathSciNet review: 0476560
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • [1] B. Bollobás and A. G. Thomason, Uniquely partitionable graphs (to appear).
  • [2] O. V. Borodin, The decomposition of graphs into degenerate subgraphs, Diskret. Analiz. Vyp. 28 Metody Diskretnogo Analiza v Teorii Grafov i Logiceskih Funkcii (1976), 3–11, 78 (Russian). MR 0498204
  • [3] 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).
  • [4] P. Catlin, A bound on the chromatic number of graphs (preprint).
  • [5] V. Chvátal, The minimality of the Mycielski graph, Graphs and combinatorics (Proc. Capital Conf., George Washington Univ., Washington, D.C., 1973) Springer, Berlin, 1974, pp. 243–246. Lecture Notes in Math., Vol. 406. MR 0360330
  • [6] V. Chvátal, The smallest triangle-free 4-chromatic 4-regular graph, J. Combinatorial Theory 9 (1970), 93–94. MR 0263691
  • [7] R. J. Cook, Point partition numbers and girth, Proc. Amer. Math. Soc. 49 (1975), 510–514. MR 0371734, 10.1090/S0002-9939-1975-0371734-8
  • [8] B. Descartes, A three-colour problem, Eureka 10 (1948), 24.
  • [9] P. Erdős, Graph theory and probability, Canad. J. Math. 11 (1959), 34–38. MR 0102081
  • [10] B. Grünbaum, A problem in graph coloring, Amer. Math. Monthly 77 (1970), 1080-1092.
  • [11] Frank Harary, Graph theory, Addison-Wesley Publishing Co., Reading, Mass.-Menlo Park, Calif.-London, 1969. MR 0256911
  • [12] Rhys Price Jones, Hereditary properties and 𝑃-chromatic numbers, Combinatorics (Proc. British Combinatorial Conf., Univ. Coll. Wales, Aberystwyth, 1973) Cambridge Univ. Press, London, 1974, pp. 83–88. London Math. Soc. Lecture Note Ser., No. 13. MR 0384590
  • [13] 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), Springer, Berlin, 1972, pp. 179–181. Lecture Notes in Math., Vol. 303. MR 0335332
  • [14] Don R. Lick and Arthur T. White, 𝑘-degenerate graphs, Canad. J. Math. 22 (1970), 1082–1096. MR 0266812
  • [15] 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 0295960
  • [16] L. Lovász, On chromatic number of finite set-systems, Acta Math. Acad. Sci. Hungar. 19 (1968), 59–67. MR 0220621
  • [17] L. Lovász, On decomposition of graphs, Studia Sci. Math. Hungar. 1 (1966), 237–238. MR 0202630
  • [18] John Mitchem, An extension of Brooks’ theorem to 𝑛-degenerate graphs, Discrete Math. 17 (1977), no. 3, 291–298. MR 0439675
  • [19] -, On extremal partitions of graphs, Ph. D. Dissertation, Western Michigan Univ., 1970, pp. 103-109.
  • [20] J. Mycielski, Sur le coloriage des graphs, Colloq. Math. 3 (1955), 161–162 (French). MR 0069494
  • [21] 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 0314705
  • [22] J. M. S. Simoes-Pereira, Joins of 𝑛-degenerate graphs and uniquely (𝑚,𝑛)-partitionable graphs, J. Combinatorial Theory Ser. B 21 (1976), no. 1, 21–29. MR 0419281
  • [23] -, On graphs uniquely partitionable into n-degenerate subgraphs, Coll. Math. Soc. Janos Bolyai, 10 Infinite and Finite Sets, Keszthely (Hungary), 1973.
  • [24] P. Turán, On the theory of graphs, Colloquium Math. 3 (1954), 19–30. MR 0062416

Similar Articles

Retrieve articles in Proceedings of the American Mathematical Society with MSC: 05C15, 05C10

Retrieve articles in all journals with MSC: 05C15, 05C10


Additional Information

DOI: http://dx.doi.org/10.1090/S0002-9939-1978-0476560-X
Keywords: n-degenerate graph, Lick-White number, genus
Article copyright: © Copyright 1978 American Mathematical Society