Pełnotekstowe zasoby PLDML oraz innych baz dziedzinowych są już dostępne w nowej Bibliotece Nauki.
Zapraszamy na https://bibliotekanauki.pl
Preferencje help
Polish version English version Język
Widoczny [Schowaj] Abstrakt
Liczba wyników

Znaleziono wyników: 3

Liczba wyników na stronie
first rewind previous Strona / 1 next fast forward last

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych:  induced subgraphs
help Sortuj według:

help Ogranicz wyniki do:
first rewind previous Strona / 1 next fast forward last
1
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Prime ideals in the lattice of additive induced-hereditary graph properties

100%
Berger A., Mihók P.
Discussiones Mathematicae Graph Theory
|
2003
|
tom 23
|
nr 1
117-127
EN
An additive induced-hereditary property of graphs is any class of finite simple graphs which is closed under isomorphisms, disjoint unions and induced subgraphs. The set of all additive induced-hereditary properties of graphs, partially ordered by set inclusion, forms a completely distributive lattice. We introduce the notion of the join-decomposability number of a property and then we prove that the prime ideals of the lattice of all additive induced-hereditary properties are divided into two groups, determined either by a set of excluded join-irreducible properties or determined by a set of excluded properties with infinite join-decomposability number. We provide non-trivial examples of each type.
2
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Minimal forbidden subgraphs of reducible graph properties

100%
Berger A.
Discussiones Mathematicae Graph Theory
|
2001
|
tom 21
|
nr 1
111-117
EN
A property of graphs is any class of graphs closed under isomorphism. Let 𝓟₁,𝓟₂,...,𝓟ₙ be properties of graphs. A graph G is (𝓟₁,𝓟₂,...,𝓟ₙ)-partitionable if the vertex set V(G) can be partitioned into n sets, {V₁,V₂,..., Vₙ}, such that for each i = 1,2,...,n, the graph $G[V_i] ∈ 𝓟_i$. We write 𝓟₁∘𝓟₂∘...∘𝓟ₙ for the property of all graphs which have a (𝓟₁,𝓟₂,...,𝓟ₙ)-partition. An additive induced-hereditary property 𝓡 is called reducible if there exist additive induced-hereditary properties 𝓟₁ and 𝓟₂ such that 𝓡 = 𝓟₁∘𝓟₂. Otherwise 𝓡 is called irreducible. An additive induced-hereditary property 𝓟 can be defined by its minimal forbidden induced subgraphs: those graphs which are not in 𝓟 but which satisfy that every proper induced subgraph is in 𝓟. We show that every reducible additive induced-hereditary property has infinitely many minimal forbidden induced subgraphs. This result is also seen to be true for reducible additive hereditary properties.
3
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Colouring graphs with prescribed induced cycle lengths

88%
Randerath B., Schiermeyer I.
Discussiones Mathematicae Graph Theory
|
2001
|
tom 21
|
nr 2
267-281
EN
In this paper we study the chromatic number of graphs with two prescribed induced cycle lengths. It is due to Sumner that triangle-free and P₅-free or triangle-free, P₆-free and C₆-free graphs are 3-colourable. A canonical extension of these graph classes is $𝓖^I(4,5)$, the class of all graphs whose induced cycle lengths are 4 or 5. Our main result states that all graphs of $𝓖^I(4,5)$ are 3-colourable. Moreover, we present polynomial time algorithms to 3-colour all triangle-free graphs G of this kind, i.e., we have polynomial time algorithms to 3-colour every $G ∈ 𝓖^I(n₁,n₂)$ with n₁,n₂ ≥ 4 (see Table 1). Furthermore, we consider the related problem of finding a χ-binding function for the class $𝓖^I(n₁,n₂)$. Here we obtain the surprising result that there exists no linear χ-binding function for $𝓖^I(3,4)$.
first rewind previous Strona / 1 next fast forward last
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.