The Slimming Number and Genus of Graphs

Guy, Richard K.

Canadian mathematical bulletin, Tome 15 (1972) no. 2, pp. 195-200

Résumé

J. Ch. Boland suggested, and Mrs. Sheehan named, the idea of the slimming number of a graph G, i.e. the minimum number, s(G), of edges, e 1e 2,..., e s, which must be removed from G in order that G—∪ e i be planar.For the complete graph, K n (n≥3), it may be seen by Euler's formula that a planar subgraph contains at most 3n—6 edges; moreover one may construct such a subgraph inductively, starting from K 3, and adding points successively, joining them to the three vertices of the region in which they lie, so 1

Détail

DOI : 10.4153/CMB-1972-035-8

Bibliographie

[1] 1. Battle, J., Harary, F., and Kodama, Y., Every planar graph with nine points has a non-planar complement, Bull. Amer. Math. Soc. 68 (1962), 569-571; M.R. 27 (1964), #5248. Google Scholar

[2] 2. Beineke, L. W., Harary, F., and Moon, J. W., On the thickness of the complete bipartite graph. Proc. Cambridge Philos. Soc, 60 (1964), 1-5; M.R. 28 (1964), #1611. Google Scholar

[3] 3. Grünbaum, B., Convex Polytopes, Interscience, New York, (1967), 61,122. Google Scholar

[4] 4. Kuratowski, K., Sur le probl#ème des courbes gauches en topologie, Fund. Math., 15 (1930), 271-283. Google Scholar

[5] 5. Ringel, G., #Über drei kombinatorische Probl#ème am n-dimensionalen W#ürfel und W#ürfelgitter, Abh. Math. Sem. Univ. Hamburg, 20 (1955), 10-19; M.R. 17 (1956), #772. Google Scholar

[6] 6. Ringel, G., Das Geschlecht des vollst#ándigen paaren Graphen, Abh. Math. Sem. Univ. Hamburg, 28 (1965), 139-150; M.R. 32 (1966), #6439. Google Scholar

[7] 7. Ringel, G., F#árbungsprobleme auf Fl#áchen und Graphen, VE. Deutsche. Verlag. Berlin. 1959; M.R. 22 (1961), #A235. Google Scholar

[8] 8. Ringel, G., The genus of graphs, in R. K. Guy, et al. (editors), Combinatorial Structures and their Applications (Proc. Calgary Internat. Conference, 1969), Gordon and Breach, New York, (1970), 361-366. Google Scholar

[9] 9. Ringel, G. and Youngs, J. W. T., Losung des problems der Nachbargebiete auf orientierbaren Fl#áchen, Arch. Math. (Basel), 20 (1969), 190-201; M.R. 39 (1970), #4049. Google Scholar

[10] 10. Ringel, G. and Youngs, J. W. T., Remarks on the Heawood conjecture, in F. Harary, (editor), Proof Techniques in Graph Theory, Academic Press, New York, (1969), 133-138. Google Scholar

[11] 11. Ringel, G. and Youngs, J. W. T., Solution of the Heawood map-coloring problem—case 11, J. Combinatorial Theory, 7 (1969), 71-93; M.R. 39 (1970), #1360. —case 2, ibid., 342-352. ? case 8, ibid., 353-363. Google Scholar

[12] 12. Terry, C. M., Welch, L. R., and Youngs, J. W. T., The Genus ofKn, n = 12(2m), Bull. Amer. Math. Soc. 71 (1965), 653-656. Ditto, n = 12s, ibid., 657-660; M.R. 31 (1966), #4022a, b. Google Scholar

[13] 13. Terry, C. M., Welch, L. R., and Youngs, J. W. T., The genus of K12s, J. Combinatorial Theory, 2 (1967), 43-60; M.R. 34 (1967), #6755. Google Scholar

[14] 14. Terry, C. M., Welch, L. R., and Youngs, J. W. T., Solution of the Heawood map-coloring problem, case 4, J. Combinatorial Theory, 8 (1970), 170-174. Google Scholar

[15] 15. Tutte, W. T., On the non-biplanar character of the complete 9-graph, Canad. Math. Bull., 6 (1963), 319-330; M.R. 28 (1964), #2535. Google Scholar

[16] 16. Youngs, J. W. T., Minimal imbeddings and the genus of a graph, J. Math. Mech., 12 (1963), 303-315; M.R. 26 (1963), #3043. Google Scholar

[17] 17. Youngs, J. W. T., The Heawood map-coloring conjecture, in F. Harary (editor), Graph Theory and Theoretical Physics, Academic Press, London, 1967, 313-354; M.R. 38 (1969), #4357. Google Scholar

[18] 18. Youngs, J. W. T., Solution of the Heawood map-coloring problem, cases 3, 5, 6 and 9. J. Combinatorial Theory, 8 (1970), 175-219. cases 1, 7 and 10, ibid., 220-231. Google Scholar