Přejít k obsahu


Induced hereditary graph classes and clousure operation

Citace: [] BROUSEK, J., SABUROV, K. Induced hereditary graph classes and clousure operation. In The 1st Young Researchers Conference on Applied Sciences. Plzeň: Západočeská univerzita, 2007. s. 37 -42. ISBN: 978-80-7043-574-8
Druh: STAŤ VE SBORNÍKU
Jazyk publikace: eng
Anglický název: Induced hereditary graph classes and clousure operation
Rok vydání: 2007
Místo konání: Plzeň
Název zdroje: Západočeská univerzita
Autoři: Jan Brousek , Khikmat Saburov
Abstrakt CZ: V tomto článku ukážeme, že když $G$ je 2-souvislý $CP_{7}$-free graf, pak $\mbox {cl}(G)$ je $CN_{112}$-free nebo $\mbox {cl}(G)$ patří do některé z 4 nekonečných tříd grafů. Rovněž ukážeme že existuje vztah mezi 2-souvislými $CN_{112}$-free a $CN$-free grafy (až na výjimky $ {\cal C}^{N}_{1},{\cal C}^{N}_{2},{\cal C}^{N}_{3},{\cal C}^{N}_{4},{\cal C}^{N}_{3a}$ a ${\cal C}^{N}_{4a}$). Z těchto výsledků vyplývá, že pokud $G$ je 3-souvislý $CP_{7}$-free graf, pak $\mbox{cl}(G)$ je $CN$-free.
Abstrakt EN: In this paper we show that if $G$ is a 2-connected $CP_{7}$-free graph, then $\mbox{cl}(G)$ is $CN_{112}$-free or $\mbox {cl}(G)$ belong to some 4 fully described infinite classes of exceptions. We also show that there is a similar relation for 2-connected $CN_{112}$-free and $CN$-free graphs (with $ {\cal C}^{N}_{1},{\cal C}^{N}_{2},{\cal C}^{N}_{3},{\cal C}^{N}_{4},{\cal C}^{N}_{3a}$ and ${\cal C}^{N}_{4a}$ at exceptions). From these propositions it follows that if $G$ is 3-connected $CP_{7}$-free graph, then $\mbox{cl}(G)$ is $CN$-free.
Klíčová slova

Zpět

Patička