Subcritical graph classes containing all planar graphs

2017/01/04 by Agelos Georgakopoulos, Stephan Wagner, Georgakopoulos, Agelos +1
Mathematics · #05A16 #05C10 #05C30 #05C80 #05C83 #Combinatorics (math.CO) #FOS: Mathematics #math.CO #msc:05A16 #msc:05C10 #msc:05C30 #msc:05C80 #msc:05C83

paper · pdf · doi:10.48550/arxiv.1701.00973

arxiv created 2018/01/05 · arxiv updated 2018/01/08

Abstract

We construct minor-closed addable families of graphs that are subcritical and contain all planar graphs. This contradicts (one direction of) a well-known conjecture of Noy.

Related

• Forbidden minors: Finding the finite few
• Free Minor Closed Classes and the Kuratowski theorem
• Universal planar graphs for the topological minor relation
• Graph product structure for non-minor-closed classes
• Quickly excluding a non-planar graph