Stars in forbidden triples generating a finite set of graphs with minimum degree four
Abstract
For a family H of graphs, a graph G is said to be H-free if G contains no member of H as a induced subgraph. Let G4(H) denote the family of connected H-free graphs having minimum degree at least 4. In this paper, we characterize the families H of connected graphs with |H|=3 such that H contains a star and G4(H) is a finite family, except for the case where {K4, K1, n}⊆H with 3 ≤ n ≤ 4.
Keywords
Full Text:
PDFDOI: http://dx.doi.org/10.5614/ejgta.2025.13.1.1
References
O. Buelban, A. Garciano, R. Marcelo, A. Mori, and S. Nakamura, Stars in forbidden triples generating a finite set of 4-connected graphs, Lecture Notes in Computer Science, Springer, in press.
R. Diestel, Graph Theory, 5th ed., Graduate Texts in Mathematics, 173, Springer, 2017.
Y. Egawa, J. Fujisawa, M. Furuya, M.D. Plummer, and A. Saito, Forbidden triples generating a finite set of 3-connected graphs, Electron. J. Combin., 22 (2015), #P3.13.
Y. Egawa and M. Furuya, Forbidden triples containing a complete graph and a complete bipartite graph of small order, Graphs Combin., 30 (2014), 1149-1162.
Y. Egawa and M. Furuya, Forbidden triples generating a finite set of graphs with minimum degree three, Discrete Applied Math., 320 (2022), 282-295.
Y. Egawa and M. Furuya, Forbidden subgraphs generating a finite set of graphs with minimum degree three and large girth, preprint.
Y. Egawa and Z. Zhao, Forbidden triples involving the complete bipartite graph with partite sets having cardinalities two and three, Ars Combin., 154 (2021), 159–195.
J. Fujisawa, M.D. Plummer, and A. Saito, Forbidden subgraphs generating a finite set, Discrete Math., 313 (2013), 1835–1842.
Refbacks
- There are currently no refbacks.
ISSN: 2338-2287
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.