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 and/or families:
“When any one of our relations was found to be a person of a very bad character, a troublesome guest, or one we desired to get rid of, upon his leaving my house I ever took care to lend him a riding-coat, or a pair of boots, or sometimes a horse of small value, and I always had the satisfaction of finding he never came back to return them.”
—Oliver Goldsmith (1728–1774)
“Happy or unhappy, families are all mysterious. We have only to imagine how differently we would be described—and will be, after our deaths—by each of the family members who believe they know us.”
—Gloria Steinem (b. 1934)