Hostname: page-component-cd9895bd7-8ctnn Total loading time: 0 Render date: 2024-12-27T06:54:14.372Z Has data issue: false hasContentIssue false
  • English
  • Français

Total Digraphs

Published online by Cambridge University Press:  20 November 2018

Gary Chartrand  and
M. James Stewart
Gary Chartrand
Affiliation:
The University of Michigan and Western Michigan University and Michigan State University
M. James Stewart
Affiliation:
The University of Michigan and Western Michigan University and Michigan State University
Rights & Permissions [Opens in a new window]

Extract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

The line - graph of an ordinary graph G is that graph whose points can be put in one-to-one correspondence with the lines of G in such a way that two points of are adjacent if and only if the corresponding lines of G are adjacent. This concept originated with Whitney [ 5 ], has the property that its (point) chromatic number equals the line chromatic number of G, where the point (line) chromatic number of graph is the minimum number of colors required to color the points (lines) of the graph such that adjacent points (lines) are colored differently.

Type
Research Article
Information
Canadian Mathematical Bulletin , Volume 9 , Issue 2 , June 1966 , pp. 171 - 176
Copyright
Copyright © Canadian Mathematical Society 1966

References

1. Behzad, M., Graphs and their chromatic numbers. Doctoral thesis, Michigan State University, 1965.Google Scholar
2. Harary, F. and Norman, R.Z., Some properties of line digraphs. Rend. Circ. Mat. Palermo 9 (1960), 161-168.Google Scholar
3. Harary, F., Norman, R. Z., and Cartwright, D., Structural models: an introduction to the theory of directed graphs. New York, 1965.Google Scholar
4. Ross, I. C. and Harary, F., The square of a tree. Bell System Tech. J. 39 (1960), 641-647.Google Scholar
5. Whitney, H., Congruent graphs and the connectivity of graphs. Amer. J. Math. 54(1932), 150-168.Google Scholar