3
$\begingroup$

I wonder, what was the first non-trivial graph class for which there was a forbidden (induced) subgraph characterisation ?

Of course, bipartite graph is one example but I am considering it as trivial because of the simplicity of the proof of sufficiency.

Another example can be planar graphs, but does Kuratowski's Theorem qualify as a forbidden subgraph characterisation ?

Do you think that the Boland-Lekkerkerker characterisation of interval graph can qualify as the first instance of non-trivial forbidden induced subgraph characterisation? Or does there exist such an example which appeared before ?

$\endgroup$
  • $\begingroup$ Boland-Lekkerkerker was published in 1962, but Dirac's 1961 paper showed that a graph whose minimal separators are cliques are characterized as graphs without induced cycles of size 4 or more, but not in this language. $\endgroup$ – JimN Aug 14 at 6:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.