Minor obstructions for apex-pseudoforests

Alexandros Leivaditis; Alexandros Singh; Giannos Stamoulis; Dimitrios M. Thilikos; Konstantinos Tsatsanis

doi:10.1016/j.disc.2021.112529

Minor obstructions for apex-pseudoforests

Alexandros Leivaditis, Alexandros Singh, Giannos Stamoulis, Dimitrios M. Thilikos, Konstantinos Tsatsanis

Computer Science

Research output: Contribution to journal › Article › peer-review

Abstract

A graph is called a pseudoforest if none of its connected components contains more than one cycle. A graph is an apex-pseudoforest if it can become a pseudoforest by removing one of its vertices. We identify 33 graphs that form the minor obstruction set of the class of apex-pseudoforests, i.e., the set of all minor-minimal graphs that are not apex-pseudoforests.

Original language	English (US)
Article number	112529
Journal	Discrete Mathematics
Volume	344
Issue number	10
DOIs	https://doi.org/10.1016/j.disc.2021.112529
State	Published - Oct 2021

Keywords

Graph minors
Minor obstructions

ASJC Scopus subject areas

Theoretical Computer Science
Discrete Mathematics and Combinatorics

Access to Document

10.1016/j.disc.2021.112529

Cite this

@article{48b51441f76c44268940219f1e3372d3,

title = "Minor obstructions for apex-pseudoforests",

abstract = "A graph is called a pseudoforest if none of its connected components contains more than one cycle. A graph is an apex-pseudoforest if it can become a pseudoforest by removing one of its vertices. We identify 33 graphs that form the minor obstruction set of the class of apex-pseudoforests, i.e., the set of all minor-minimal graphs that are not apex-pseudoforests.",

keywords = "Graph minors, Minor obstructions",

author = "Alexandros Leivaditis and Alexandros Singh and Giannos Stamoulis and Thilikos, {Dimitrios M.} and Konstantinos Tsatsanis",

note = "Publisher Copyright: {\textcopyright} 2021 Elsevier B.V.",

year = "2021",

month = oct,

doi = "10.1016/j.disc.2021.112529",

language = "English (US)",

volume = "344",

journal = "Discrete Mathematics",

issn = "0012-365X",

publisher = "Elsevier B.V.",

number = "10",

}

TY - JOUR

T1 - Minor obstructions for apex-pseudoforests

AU - Leivaditis, Alexandros

AU - Singh, Alexandros

AU - Stamoulis, Giannos

AU - Thilikos, Dimitrios M.

AU - Tsatsanis, Konstantinos

PY - 2021/10

Y1 - 2021/10

N2 - A graph is called a pseudoforest if none of its connected components contains more than one cycle. A graph is an apex-pseudoforest if it can become a pseudoforest by removing one of its vertices. We identify 33 graphs that form the minor obstruction set of the class of apex-pseudoforests, i.e., the set of all minor-minimal graphs that are not apex-pseudoforests.

AB - A graph is called a pseudoforest if none of its connected components contains more than one cycle. A graph is an apex-pseudoforest if it can become a pseudoforest by removing one of its vertices. We identify 33 graphs that form the minor obstruction set of the class of apex-pseudoforests, i.e., the set of all minor-minimal graphs that are not apex-pseudoforests.

KW - Graph minors

KW - Minor obstructions

UR - http://www.scopus.com/inward/record.url?scp=85111033383&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85111033383&partnerID=8YFLogxK

U2 - 10.1016/j.disc.2021.112529

DO - 10.1016/j.disc.2021.112529

M3 - Article

AN - SCOPUS:85111033383

SN - 0012-365X

VL - 344

JO - Discrete Mathematics

JF - Discrete Mathematics

IS - 10

M1 - 112529

ER -

Minor obstructions for apex-pseudoforests

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this