Temat: hereditary classes - Katalog OPAC zbiorów

Skocz do pozycji: 1.

Tytuł:: On a perfect problem
Autorzy:: Zverovich, Igor
Powiązania:: https://bibliotekanauki.pl/articles/743945.pdf
Data publikacji:: 2006
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:: hereditary classes
perfect graphs
Opis:: We solve Open Problem (xvi) from Perfect Problems of Chvátal [1] available at ftp://dimacs.rutgers.edu/pub/perfect/problems.tex: Is there a class C of perfect graphs such that (a) C does not include all perfect graphs and (b) every perfect graph contains a vertex whose neighbors induce a subgraph that belongs to C? A class P is called locally reducible if there exists a proper subclass C of P such that every graph in P contains a local subgraph belonging to C. We characterize locally reducible hereditary classes. It implies that there are infinitely many solutions to Open Problem (xvi). However, it is impossible to find a hereditary class C of perfect graphs satisfying both (a) and (b).
Źródło:: Discussiones Mathematicae Graph Theory; 2006, 26, 2; 273-277
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ł:: 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

Skocz do pozycji: 3.

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: 4.

Tytuł:: Unique factorisation of additive induced-hereditary properties
Autorzy:: Farrugia, Alastair
Richter, R.
Powiązania:: https://bibliotekanauki.pl/articles/744519.pdf
Data publikacji:: 2004
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:: additive and hereditary graph classes
unique factorization
Opis:: An additive hereditary graph property is a set of graphs, closed under isomorphism and under taking subgraphs and disjoint unions. Let ₁,...,ₙ be additive hereditary graph properties. A graph G has property (₁∘...∘ₙ) if there is a partition (V₁,...,Vₙ) of V(G) into n sets such that, for all i, the induced subgraph $G[V_i]$ is in $_i$. A property is reducible if there are properties , such that = ∘ ; otherwise it is irreducible. Mihók, Semanišin and Vasky [8] gave a factorisation for any additive hereditary property into a given number dc() of irreducible additive hereditary factors. Mihók [7] gave a similar factorisation for properties that are additive and induced-hereditary (closed under taking induced-subgraphs and disjoint unions). Their results left open the possiblity of different factorisations, maybe even with a different number of factors; we prove here that the given factorisations are, in fact, unique.
Źródło:: Discussiones Mathematicae Graph Theory; 2004, 24, 2; 319-343
2083-5892
Pojawia się w:: Discussiones Mathematicae Graph Theory
Dostawca treści:: Biblioteka Nauki

Artykuł

Zmień widok

na półce

Informacja

Wyszukujesz frazę "hereditary classes" wg kryterium: Temat

Źródło danych

Dostawca treści

Kolekcja

Rok wydania

Wydawca

Temat

Autor

Typ dokumentu

Język