Skip to content
DraconiticResearch
Search Sources API
203,234 studies31 sourcesUpdated 48 min ago
PreprintCC BY 4.0arXiv

Non-induced inherent graphs

  • Vladimir Gurvich
  • Matjaž Krnc
  • Martin Milanič
  • Mikhail Vyalyi
Open at sourcePDFDOICite

Abstract

Concepts of avoidable paths and inherent two-rooted graphs were recently introduced for the case of induced subgraphs. In this paper, we translate this framework to the setting of not necessarily induced (NNI) subgraphs, where the structural constraints, as well as conclusions, are significantly relaxed. We develop a new sufficient condition for inherence, and use it to provide complete characterizations of inherent two-rooted paths and forks. We show that for these families, the obvious necessary condition for inherence from the induced case is sufficient in the NNI setting. To complement these results, we introduce two general methods for proving non-inherence and apply them to demonstrate the non-inherence of several classes of two-rooted trees. Keywords: subgraph, two-rooted graph, two-rooted tree, avoidable two-rooted graph, inherent two-rooted graph

Related

  1. Long induced cycles in pseudorandom graphs
    Sahar Diskin, Lyuben Lichev, Michael Krivelevich +1
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv
  2. A Note on Vertex-Critical Induced Subgraphs of Shift Graphs
    Tomáš Kaiser, Matěj Stehlík, Riste Škrekovski +1
    The Electronic Journal of CombinatoricsPeer-reviewedCC BY 4.0Full textCombinatorics & discrete mathematicsCrossref
  3. Coloring graphs with no long induced path
    Sang-il Oum
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  4. Induced Forest Minor Theorem for Graphs Without an Induced Star
    Robert Hickingbotham, Gwenaël Joret
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  5. Revisiting separators in string graphs, region intersection graphs, and induced-minor-free graphs
    James Davies, Paweł Rzążewski, Jack Spalding-Jamieson +1
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsGeometry & topologyarXiv

Cite

BibTeXRIS
BibTeX
@misc{gurvich2026noninduced,
  title = {{Non-induced inherent graphs}},
  author = {Vladimir Gurvich and Matjaž Krnc and Martin Milanič and Mikhail Vyalyi},
  howpublished = {arXiv},
  year = {2026},
  month = nov,
  doi = {10.48550/arxiv.2611.06636},
  eprint = {2611.06636},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.06636},
  note = {CC BY 4.0},
}
RIS
TY  - UNPB
TI  - Non-induced inherent graphs
AU  - Vladimir Gurvich
AU  - Matjaž Krnc
AU  - Martin Milanič
AU  - Mikhail Vyalyi
PY  - 2026
DA  - 2026/11/04
PB  - arXiv
DO  - 10.48550/arxiv.2611.06636
UR  - https://arxiv.org/abs/2611.06636
AB  - Concepts of avoidable paths and inherent two-rooted graphs were recently introduced for the case of induced subgraphs. In this paper, we translate this framework to the setting of not necessarily induced (NNI) subgraphs, where the structural constraints, as well as conclusions, are significantly relaxed. We develop a new sufficient condition for inherence, and use it to provide complete characterizations of inherent two-rooted paths and forks. We show that for these families, the obvious necessary condition for inherence from the induced case is sufficient in the NNI setting. To complement these results, we introduce two general methods for proving non-inherence and apply them to demonstrate the non-inherence of several classes of two-rooted trees. Keywords: subgraph, two-rooted graph, two-rooted tree, avoidable two-rooted graph, inherent two-rooted graph
ER  -