On the genus of graphs with Lick-White number 𝑘

Mitchem, John

doi:10.1090/S0002-9939-1978-0476560-X

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

Uniquely partitionable graphs

O. V. Borodin, The decomposition of graphs into degenerate subgraphs, Diskret. Analiz (1976), 3–11, 78 (Russian). MR 498204

On an upper bound of the graph’s chromatic number depending on graph’s degree and density

A bound on the chromatic number of graphs

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

A three-colour problem

10

P. Erdős, Graph theory and probability, Canadian J. Math. 11 (1959), 34–38. MR 102081, DOI 10.4153/CJM-1959-003-9

A problem in graph coloring

77

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

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

P. Turán, On the theory of graphs, Colloq. Math. 3 (1954), 19–30. MR 62416, DOI 10.4064/cm-3-1-19-30