Wszystkie pola: forbidden graph - Katalog OPAC zbiorów

Skocz do pozycji: 1.

Tytuł:: Cardinality of a minimal forbidden graph family for reducible additive hereditary graph properties
Autorzy:: Drgas-Burchardt, Ewa
Powiązania:: https://bibliotekanauki.pl/articles/743169.pdf
Data publikacji:: 2009
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:: hereditary graph property
lattice of additive hereditary graph properties
minimal forbidden graph family
join in the lattice
reducibility
Opis:: An additive hereditary graph property is any class of simple graphs, which is closed under isomorphisms unions and taking subgraphs. Let $L^a$ denote a class of all such properties. In the paper, we consider H-reducible over $L^a$ properties with H being a fixed graph. The finiteness of the sets of all minimal forbidden graphs is analyzed for such properties.
Źródło:: Discussiones Mathematicae Graph Theory; 2009, 29, 2; 263-274
2083-5892
Pojawia się w:: Discussiones Mathematicae Graph Theory
Dostawca treści:: Biblioteka Nauki

Artykuł

Zmień widok

na półce

Skocz do pozycji: 2.

Tytuł:: Forbidden Structures for Planar Perfect Consecutively Colourable Graphs
Autorzy:: Borowiecka-Olszewska, Marta
Drgas-Burchardt, Ewa
Powiązania:: https://bibliotekanauki.pl/articles/31341980.pdf
Data publikacji:: 2017-05-01
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:: edge colouring
consecutive (interval) colouring
deficiency
Sevastjanov graph
forbidden graph
Opis:: A consecutive colouring of a graph is a proper edge colouring with posi- tive integers in which the colours of edges incident with each vertex form an interval of integers. The idea of this colouring was introduced in 1987 by Asratian and Kamalian under the name of interval colouring. Sevast- janov showed that the corresponding decision problem is NP-complete even restricted to the class of bipartite graphs. We focus our attention on the class of consecutively colourable graphs whose all induced subgraphs are consecutively colourable, too. We call elements of this class perfect consecutively colourable to emphasise the conceptual similarity to perfect graphs. Obviously, the class of perfect consecutively colourable graphs is induced hereditary, so it can be characterized by the family of induced forbidden graphs. In this work we give a necessary and sufficient conditions that must be satisfied by the generalized Sevastjanov rosette to be an induced forbid- den graph for the class of perfect consecutively colourable graphs. Along the way, we show the exact values of the deficiency of all generalized Sevastjanov rosettes, which improves the earlier known estimating result. It should be mentioned that the deficiency of a graph measures its closeness to the class of consecutively colourable graphs. We motivate the investigation of graphs considered here by showing their connection to the class of planar perfect consecutively colourable graphs.
Źródło:: Discussiones Mathematicae Graph Theory; 2017, 37, 2; 315-336
2083-5892
Pojawia się w:: Discussiones Mathematicae Graph Theory
Dostawca treści:: Biblioteka Nauki

Artykuł

Zmień widok

na półce

Skocz do pozycji: 3.

Tytuł:: A note on joins of additive hereditary graph properties
Autorzy:: Drgas-Burchardt, Ewa
Powiązania:: https://bibliotekanauki.pl/articles/743593.pdf
Data publikacji:: 2006
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:: hereditary property
lattice of additive hereditary graph properties
minimal forbidden subgraph family
join in the lattice
Opis:: Let $L^a$ denote a set of additive hereditary graph properties. It is a known fact that a partially ordered set $(L^a, ⊆ )$ is a complete distributive lattice. We present results when a join of two additive hereditary graph properties in $(L^a, ⊆ )$ has a finite or infinite family of minimal forbidden subgraphs.
Źródło:: Discussiones Mathematicae Graph Theory; 2006, 26, 3; 413-418
2083-5892
Pojawia się w:: Discussiones Mathematicae Graph Theory
Dostawca treści:: Biblioteka Nauki

Artykuł

Zmień widok

na półce

Skocz do pozycji: 4.

Tytuł:: $ \mathcal{P} $-Apex Graphs
Autorzy:: Borowiecki, Mieczysław
Drgas-Burchardt, Ewa
Sidorowicz, Elżbieta
Powiązania:: https://bibliotekanauki.pl/articles/31342421.pdf
Data publikacji:: 2018-05-01
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:: induced hereditary classes of graphs
forbidden subgraphs
hypergraphs
transversal number
Opis:: Let $ \mathcal{P} $ be an arbitrary class of graphs that is closed under taking induced subgraphs and let $ \mathcal{C}( \mathcal{P} ) $ be the family of forbidden subgraphs for $ \mathcal{P} $. We investigate the class $ \mathcal{P} (k) $ consisting of all the graphs $ G $ for which the removal of no more than $ k $ vertices results in graphs that belong to $ \mathcal{P} $. This approach provides an analogy to apex graphs and apex-outerplanar graphs studied previously. We give a sharp upper bound on the number of vertices of graphs in $ \mathcal{C}( \mathcal{P}(1)) $ and we give a construction of graphs in $ \mathcal{C}( \mathcal{P}(k)) $ of relatively large order for $ k \ge 2 $. This construction implies a lower bound on the maximum order of graphs in $ \mathcal{C}( \mathcal{P}(k)) $. Especially, we investigate $ \mathcal{C}( \mathcal{W}_r(1)) $, where $ \mathcal{W}_r $ denotes the class of $ \mathcal{P}_r $-free graphs. We determine some forbidden subgraphs for the class $ \mathcal{W}_r(1) $ with the minimum and maximum number of vertices. Moreover, we give sufficient conditions for graphs belonging to $ \mathcal{C} ( \mathcal{P} (k)) $, where $ \mathcal{P} $ is an additive class, and a characterisation of all forests in $ \mathcal{C} ( \mathcal{P} (k)) $. Particularly we deal with $ \mathcal{C} ( \mathcal{P} (1)) $, where $ \mathcal{P} $ is a class closed under substitution and obtain a characterisation of all graphs in the corresponding $ \mathcal{C} ( \mathcal{P} (1)) $. In order to obtain desired results we exploit some hypergraph tools and this technique gives a new result in the hypergraph theory.
Źródło:: Discussiones Mathematicae Graph Theory; 2018, 38, 2; 323-349
2083-5892
Pojawia się w:: Discussiones Mathematicae Graph Theory
Dostawca treści:: Biblioteka Nauki

Artykuł

Zmień widok

na półce

Skocz do pozycji: 5.

Tytuł:: Sum-List Colouring of Unions of a Hypercycle and a Path with at Most Two Vertices in Common
Autorzy:: Drgas-Burchardt, Ewa
Sidorowicz, Elżbieta
Powiązania:: https://bibliotekanauki.pl/articles/31527293.pdf
Data publikacji:: 2020-08-01
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:: hypergraphs
sum-list colouring
induced hereditary classes
forbidden hypergraphs
Opis:: Given a hypergraph $\mathcal{H}$ and a function $f : V (\mathcal{H}) → ℕ$, we say that $\mathcal{H}$ is $f$-choosable if there is a proper vertex colouring $ϕ$ of $\mathcal{H}$ such that $ϕ (v) ∈ L(v)$ for all $v ∈ V (\mathcal{H})$, where $L : V (\mathcal{H}) → 2^ℕ$ is any assignment of $f(v)$ colours to a vertex $v$. The sum choice number $\mathcal{H}i_{sc}(\mathcal{H})$ of $\mathcal{H}$ is defined to be the minimum of $Σ_{v∈V(\mathcal{H})}f(v)$ over all functions $f$ such that $\mathcal{H}$ is $f$-choosable. For an arbitrary hypergraph $\mathcal{H}$ the inequality $χ_{sc}(\mathcal{H}) ≤ |V (\mathcal{H})| + |ɛ (\mathcal{H})|$ holds, and hypergraphs that attain this upper bound are called $sc$-greedy. In this paper we characterize $sc$-greedy hypergraphs that are unions of a hypercycle and a hyperpath having at most two vertices in common. Consequently, we characterize the hypergraphs of this type that are forbidden for the class of $sc$-greedy hypergraphs.
Źródło:: Discussiones Mathematicae Graph Theory; 2020, 40, 3; 893-917
2083-5892
Pojawia się w:: Discussiones Mathematicae Graph Theory
Dostawca treści:: Biblioteka Nauki

Artykuł

Zmień widok

na półce

Informacja

Wyszukujesz frazę "forbidden graph" wg kryterium: Wszystkie pola

Źródło danych

Dostawca treści

Kolekcja

Rok wydania

Wydawca

Temat

Autor

Typ dokumentu

Język