Hostname: page-component-cd9895bd7-dzt6s Total loading time: 0 Render date: 2024-12-28T14:10:47.625Z Has data issue: false hasContentIssue false
  • English
  • Français

A criterion for the planarity of the total graph of a graph*

Published online by Cambridge University Press:  24 October 2008

Mehdi Behzad
Mehdi Behzad
Affiliation:
Wayne State University and Pahlavi University, Shiraz, Iran
Get access Rights & Permissions [Opens in a new window]

Extract

Two well-known numbers associated with a graph G (finite and undirected with no loops or multiple lines) are the (point) chromatic and the line chromatic number of G (see (2)). With G there is associated a graph L(G), called the line-graph of G, such that the line chromatic number of G is the same as the chromatic number of L(G). This concept was originated by Whitney (9) in 1932. In 1963, Sedlâček (8) characterized graphs with planar line-graphs. In this note we introduce the notions of the total chromatic number and the total graph of a graph, and characterize graphs with planar total graphs.

Type
Research Article
Information
Mathematical Proceedings of the Cambridge Philosophical Society , Volume 63 , Issue 3 , July 1967 , pp. 679 - 681
Copyright
Copyright © Cambridge Philosophical Society 1967

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

REFERENCES

(1)Behzad, M. Graphs and their chromatic numbers. Ph.D. Thesis, Michigan State University (1965).Google Scholar
(2)Behzad, M., Chartrand, G. and Cooper, J. K. JrThe color numbers of complete graphs. J. London Math. Soc. 42 (1967), 226–228.CrossRefGoogle Scholar
(3)Harary, F., Karp, R. M. and Tutte, W. T.A Criterion for Planarity of the Square of a Graph, to appear.Google Scholar
(4)Harary, F. and Ross, I. C.The square of a tree. The Bell System Tech. J. 39 (1960), 641–647.Google Scholar
(5)König, D.Theorie der endlichen und unendlichen Graphen (Leipzig, 1936; reprinted New York, 1950).Google Scholar
(6)Kuratowski, G.Sur le problême des courbes gauches en topologie. Fund. Math. 15 (1930), 271–283.CrossRefGoogle Scholar
(7)Ore, O.Theory of Graphs (Providence, 1962).CrossRefGoogle Scholar
(8)Sedlâček, J.Theory of Graphs and its Applications (Czechos. Academy of Sciences and Academic Press, 1963).Google Scholar
(9)Whitney, H.Congruent graphs and the connectivity of graphs. Amer. J. Math. (1932), 150–168.CrossRefGoogle Scholar