A forbidden pair for connected graphs to have spanning k-trees

Shun ichi Maezawa, Kenta Ozeki

Research output: Contribution to journalArticlepeer-review


For an integer (Formula presented.), a (Formula presented.) -tree is a tree with maximum degree at most (Formula presented.). A (Formula presented.) -tree containing all vertices of a graph (Formula presented.) is called a spanning (Formula presented.) -tree of (Formula presented.). In 2010, Ota and Sugiyama gave a forbidden induced subgraph condition for a graph to have a spanning (Formula presented.) -tree and they posed a conjecture that is stronger than their result. In this paper, we solve their conjecture.

Original languageEnglish
Pages (from-to)509-519
Number of pages11
JournalJournal of Graph Theory
Issue number3
Publication statusPublished - Mar 2022


Dive into the research topics of 'A forbidden pair for connected graphs to have spanning k-trees'. Together they form a unique fingerprint.

Cite this