Abstract of Colloquium talk at Math Department of WVU, February 6, 1997

Professor Lubo Soltes

Visiting Professor at West Virginia University

Problems on Line Graphs

The line graph operator is one of the most natural operators in graph theory. The line graph of a given graph G is the graph whose vertices are the edges of the graph G, with two vertices adjacent whenever the corresponding edges in G are.

The concept of line graphs emerged in the early days of graph theory, and most classical problems on them have been resolved in the 60th and early 70th. Recent research on line graphs has often been inspired by a conjecture asserting that each four-connected line graph contains a cycle visiting each vertex, which is still open.

We will discuss early work on line graphs and then will focus on characterizations of the range of the line graph operator and the applications of these results.