k-Degenerate Graphs

Canadian journal of mathematics, Tome 22 (1970) no. 5, pp. 1082-1096

Résumé

Graphs possessing a certain property are often characterized in terms of a type of configuration or subgraph which they cannot possess. For example, a graph is totally disconnected (or, has chromatic number one) if and only if it contains no lines; a graph is a forest (or, has point-arboricity one) if and only if it contains no cycles. Chartrand, Geller, and Hedetniemi [2] defined a graph to have property Pn if it contains no subgraph homeomorphic from the complete graph K n+1 or the complete bipartite graph For the first four natural numbers n, the graphs with property Pn are exactly the totally disconnected graphs, forests, outerplanar and planar graphs, respectively. This unification suggested the extension of many results known to hold for one of the above four classes of graphs to one or more of the remaining classes.

Détail

DOI : 10.4153/CJM-1970-125-1

Bibliographie

[1] 1. Behzad, M. and Chartrand, G., An introduction to the theory of graphs (Allyn and Bacon, to appear). Google Scholar

[2] 2. Chartrand, G., Geller, D., and Hedetniemi, S., Graphs with forbidden subgraphs, J. Combinatorial Theory (to appear). Google Scholar

[3] 3. Chartrand, G. and Kronk, H., The point-arboricity of planar graphs, J. London Math. Soc. 44 (1969), 612–616. Google Scholar

[4] 4. Chartrand, G., Kronk, H., and Wall, C., The point-arboricity of a graph, Israel J. Math. 6 (1968), 169–175. Google Scholar

[5] 5. Dirac, G. A., A property of 4-chromatic graphs and some remarks on critical graphs, J. London Math. Soc. 27 (1952), 85–92. Google Scholar

[6] 6. Dirac, G. A., Some theorems on abstract graphs, Proc. London Math. Soc, Ser. 3, 2 (1952), 69–81. Google Scholar

[7] 7. Dirac, G. A., The structure of k-chromatic graphs, Fund. Math. 40 (1953), 42–55. Google Scholar

[8] 8. Harary, F., Graph theory (Addison-Wesley, Reading, Massachusetts, 1969). Google Scholar

[9] 9. Lick, D. R. and White, A. T., Chromatic-durable graphs (submitted for publication). Google Scholar

[10] 10. Mitchem, J., On extremal partitions of graphs, Thesis, Western Michigan University, Kalamazoo, Michigan, 1970. Google Scholar

[11] 11. Szekeres, G. and Wilf, H. S., An inequality for the chromatic number of a graph, J. Combinatorial Theory 4 (1968), 1–3. Google Scholar

[12] 12. Wilf, H. S., The eigenvalues of a graph and its chromatic number, J. London Math. Soc. 42 (1967), 330–332. Google Scholar