Search

Chromatic graph theory is one of the most studied areas of graph theory, and this chapter looks at some of the problems that have line graph connections. A basic relationship is the fact that coloring the edges of a graph is equivalent to coloring the vertices of its line graph. In fact, this fact provides us with a line graph version of the four color theorem. The line graphs of cubic graphs constitute an interesting family on their own: it is known that their chromatic number is either 3 or 4, but which is a hard problem, and aspects of this are discussed here. We then proceed on to the general line graph problem with theorems that state that the line graph of a graph G with maximum degree Δ has chromatic number either Δ or Δ + 1 and it is always Δ if G is bipartite. The chapter concludes with modifications of the standard coloring requirement, one stronger and one weaker, and also results on coloring line graphs of multigraphs.

The variant of line graphs that is the main subject of this chapter has the basic element of a path of length 2 as a vertex, with adjacency of two of these vertices being given by their having a path of length 1 in common and their union being either a path or cycle of length 3. After proving some basic results, we turn to the characterization of path graphs, the main theorem being an analogue of Krausz’s partition characterization for line graphs themselves, but more complicated. This is followed by isomorphism results, and then material on path digraphs, the directed analogue of path graphs. The chapter concludes with yet another variation of line graphs, the intersection graph of the cliques (the maximal complete subgraphs) of a graph. The main result here is their characterization with a requirement of a common intersection property.

Graphs and matrices have an intimate connection, and this naturally carries over to line digraphs. The foremost basic result in this area is Horst Sachs’s theorem which states that eigenvalues of the adjacency matrix of a line graph are never less than −2. This feature pervades this chapter, culminating in a powerful theorem of Cameron, Goethals, Seidel, and Shult on root systems.

This, the last chapter of the book, might be called ‘beyond line graphs’ because most of the graphs under consideration are not in fact line graphs. Recall that Krausz’s characterization theorem was this: A graph is a line graph if and only if its edges can be partitioned into complete subgraphs in such a way that each vertex is in just one or two of the subgraphs. Here, we extend this idea and define the Krausz dimension of a graph G to be the minimum value of d for which the edge set of G can be partitioned into complete subgraphs in such a way that each vertex is in at most d of the subgraphs. This turns out to be an NP-complete parameter, and so our focus is on bounds and critical graphs.

The precursor of line graphs as an object of study was in isomorphisms between graphs and automorphisms of graphs. Consider a one-to-one function from the edges of a graph with three edges with a common vertex and a graph with three edges forming a cycle. As shown by Hassler Whitney, this mapping not only preserves adjacency of edges, but these two are the only connected non-isomorphic graphs with this property. Whitney also proved that there are just three connected graphs having automorphisms in which three edges forming triangles and Y-graphs get interchanged. Groups connected with line graphs are also explored in this chapter, and it concludes with an interesting result on graphs that are not only isomorphic to their line graph but with their vertex-sets being preserved.

Instead of simply taking, from a given graph G, one edge at a time to form the line graph, one could take pairs of edges as the vertices and let two of these vertices be adjacent if at least one of the edges in one set is adjacent in G to at least one of those in the other set. This new graph is called a line graph of index 2. Naturally, line graphs of index k are defined analogously, and they constitute the subject of this chapter and have the name super line graphs. Subgraphs, independent sets, and paths and cycles are among the aspects of these objects that are discussed in subsequent sections. The case k = 2 is the examined in greater detail. We then turn to what we call the ‘line-completion number’ of a graph G, which is the least index r for which the super line graph is complete. This turns out to be particularly interesting as a purely number-theoretical problem that is difficult to compute or even approximate in many cases. We then conclude the chapter with sections on super line digraphs and super line multigraphs.

As investigation of the concept of a line graph has led to many interesting results, it is natural to expect that there has also been meaningful research into variations and generalizations of the subject. In this, the first of several chapters on such topics, instead of just the edges of a given graph becoming the vertices of a new graph, both the vertices and the edges of the original become vertices. The new graph is called the total graph of the original, and of course adjacency in the total graph has an appropriate definition, combining incidence and adjacency from the original graph. It so happens that total graphs have a nice alternative description in terms first of replacing the edges of a graph by paths of length 2 and then joining by an edge any vertices at distance 2. After some elementary properties of total graphs results on planarity, Eulerian and Hamiltonian total graphs are analyzed. The chapter concludes with results on total digraphs, which behave quite differently from total graphs.

Signed graphs are another interesting variation of graphs, usually taken to be graphs in which each edge is either positive or negative. In the literature, there is more than one option for the rule for the labels on the edges of the line graph, and two of these will be considered here. It is therefore useful for us to use different symbols for the signs in the two cases, and hence different arithmetic formulas for the line-graph rule. In the first kind, we use + and − with the rule being the common product of signs. The focus in the resulting signed line graph is whether all cycles have a positive value. In the second, we use 0 and 1 and the rule is the Boolean binary sum. The focus in the resulting signed line graph is on Boolean properties and special colorings.

In this last chapter of Part I, the focus is on local relationships between elements of a line graph. Among these are discrete analogues of the geometric concepts of diameter, radius, and center. Some of the results involve connections for these quantities between graphs and their line graphs, and what happens to their values in iterated line graphs. The center of a graph is also defined in a natural way, and some intriguing results on the center of a line graph are described. The other topic is in response to a question about partially ordered sets: Which line graphs can their edges oriented so that the result is a transitive ordering? The answer can be given in terms of forbidden subgraphs.

In this chapter we look first at which line graphs are Eulerian and which graphs are the line graphs of Eulerian graphs, both of which have nice characterizations. We then turn to the subject of Hamiltonian graphs. It is not hard to show that the line graph of a Hamiltonian graph is Hamiltonian, but as one would expect, determining which line graphs are Hamiltonian is a difficult problem. The fourth section is devoted to aspects of an outstanding conjecture on this subject: if a line graph is 4-connected, then it is Hamiltonian. We then turn to iterated line graphs. After observing that unless a graph is a path, all of its iterations beyond some point are Hamiltonian, and the problem of determining when this first iteration occurs investigated in the last section.

Unlike iterated line graphs, where, with the exception of paths, cycles, and the claw, the number of vertices increases monotonically after possibly one step, more interesting things can happen, one being that connectedness is not necessarily preserved. Another instance is that a digraph can be isomorphic to its second iterated line digraph but not to its first. In more general terms, there are digraphs for which, after a while, the sequence of iterated line digraphs becomes periodic. This is just one of the interesting features of this chapter. In addition, second-order line digraphs are characterized, a result that is quite complicated. This is followed by its application to some special classes of digraphs.