Relations To Other Families of Graphs
Every line graph is a claw-free graph. Some of the properties of claw-free graphs are generalizations of those of line graphs.
The line graph of a bipartite graph is perfect (see König's theorem). The line graphs of bipartite graphs form one of the key building blocks of perfect graphs, used in the proof of the perfect graph theorem. A special case is the rook's graphs, line graphs of complete bipartite graphs.
Read more about this topic: Line Graph
Famous quotes containing the words relations to, relations and/or families:
“The interest in life does not lie in what people do, nor even in their relations to each other, but largely in the power to communicate with a third party, antagonistic, enigmatic, yet perhaps persuadable, which one may call life in general.”
—Virginia Woolf (1882–1941)
“Words are but symbols for the relations of things to one another and to us; nowhere do they touch upon absolute truth.”
—Friedrich Nietzsche (1844–1900)
“The brotherhood of men does not imply their equality. Families have their fools and their men of genius, their black sheep and their saints, their worldly successes and their worldly failures. A man should treat his brothers lovingly and with justice, according to the deserts of each. But the deserts of every brother are not the same.”
—Aldous Huxley (1894–1963)