See about middle of the page a description of Simon Smith’s talk at BMC.

The day began with the plenary talk by Paul Seymour, whom I’ve known for longer than almost anyone else at the meeting.

He explained that there are many different “ordering” relations on graphs; the two he considers most important are the minor and induced subgraph orders. Roughly speaking, he worked on the minor ordering in the second millennium and the induced subgraph ordering in the third.

An induced subgraph of a graph is obtained by throwing away some vertices and the edges incident with them; you are not allowed to throw away an edge within the set of vertices you are keeping. Paul began with the general problem: given a graph *H*, can you determine the structure of graphs *G* containing no induced copy of *H*?

The first issue is what you mean by “structure” here. Paul thinks of it as a construction for such graphs. But even…

View original post 1,611 more words

%d bloggers like this: