The question of whether there is a logic that captures polynomial time was
formulated by Yuri Gurevich in 1988. It is still wide open and regarded as one
of the main open problems in finite model theory and database theory. Partial
results have been obtained for specific classes of structures. In particular,
it is known that fixed-point logic with counting captures polynomial time on
all classes of graphs with excluded minors. The introductory part of this paper
is a short survey of the state-of-the-art in the quest for a logic capturing
polynomial time.

The main part of the paper is concerned with classes of graphs defined by
excluding induced subgraphs. Two of the most fundamental such classes are the
class of chordal graphs and the class of line graphs. We prove that capturing
polynomial time on either of these classes is as hard as capturing it on the
class of all graphs. In particular, this implies that fixed-point logic with
counting does not capture polynomial time on these classes. Then we prove that
fixed-point logic with counting does capture polynomial time on the class of
all graphs that are both chordal and line graphs.