2020/04/18 by Ajit A. Diwan
Computer Science · Mathematics · #1-planar graph #Advanced Graph Theory Research #Chordal graph #Combinatorics #Conjecture #Degenerate energy levels #Degree (music) #Discrete mathematics #Finite Group Theory Research #Graph #Limits and Structures in Graph Theory #Mathematics #Physics #Planar graph #Subdivision #math.CO #msc:05C
paper · pdf · doi:10.1002/jgt.22818
arxiv created 2020/04/18 · openalex publication_date 2022/03/11 · arxiv updated 2022/03/15 · openalex created_date 2022/04/03 · openalex updated_date 2026/08/05
We prove that every graph of minimum degree at least d ≥ 1 contains a subdivision of some maximal 3-degenerate graph of order d+1. This generalizes the classic results of Dirac (d=3) and Pelikán (d=4). We conjecture that for any planar maximal 3-degenerate graph H of order d+1 and any graph G of minimum degree at least d, G contains a subdivision of H. We verify this in the case H is P63 and P73