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: 5

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

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych:  forbidden 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

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.
2
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

2-factors in claw-free graphs

100%
Chen G., Faudree J., Gould R., Saito A.
Discussiones Mathematicae Graph Theory
|
2000
|
tom 20
|
nr 2
165-172
EN
We consider the question of the range of the number of cycles possible in a 2-factor of a 2-connected claw-free graph with sufficiently high minimum degree. (By claw-free we mean the graph has no induced $K_{1,3}$.) In particular, we show that for such a graph G of order n ≥ 51 with δ(G) ≥ (n-2)/3, G contains a 2-factor with exactly k cycles, for 1 ≤ k ≤ (n-24)/3. We also show that this result is sharp in the sense that if we lower δ(G), we cannot obtain the full range of values for k.
3
Content available remote

Chromatic Sums for Colorings Avoiding Monochromatic Subgraphs

100%
Kubicka E., Kubicki G., McKeon K. A.
Discussiones Mathematicae Graph Theory
|
2015
|
tom 35
|
nr 3
541-555
EN
Given graphs G and H, a vertex coloring c : V (G) →ℕ is an H-free coloring of G if no color class contains a subgraph isomorphic to H. The H-free chromatic number of G, χ (H,G), is the minimum number of colors in an H-free coloring of G. The H-free chromatic sum of G, ∑(H,G), is the minimum value achieved by summing the vertex colors of each H-free coloring of G. We provide a general bound for ∑(H,G), discuss the computational complexity of finding this parameter for different choices of H, and prove an exact formulas for some graphs G. For every integer k and for every graph H, we construct families of graphs, Gk with the property that k more colors than χ (H,G) are required to realize ∑(H,G) for H-free colorings. More complexity results and constructions of graphs requiring extra colors are given for planar and outerplanar graphs.
4
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Towards a characterization of bipartite switching classes by means of forbidden subgraphs

100%
Hage J., Harju T.
Discussiones Mathematicae Graph Theory
|
2007
|
tom 27
|
nr 3
471-483
EN
We investigate which switching classes do not contain a bipartite graph. Our final aim is a characterization by means of a set of critically non-bipartite graphs: they do not have a bipartite switch, but every induced proper subgraph does. In addition to the odd cycles, we list a number of exceptional cases and prove that these are indeed critically non-bipartite. Finally, we give a number of structural results towards proving the fact that we have indeed found them all. The search for critically non-bipartite graphs was done using software written in C and Scheme. We report on our experiences in coping with the combinatorial explosion.
5
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Forbidden triples implying Hamiltonicity: for all graphs

100%
Faudree R., Gould R., Jacobson M.
Discussiones Mathematicae Graph Theory
|
2004
|
tom 24
|
nr 1
47-54
EN
In [2], Brousek characterizes all triples of graphs, G₁, G₂, G₃, with $G_i = K_{1,3}$ for some i = 1, 2, or 3, such that all G₁G₂G₃-free graphs contain a hamiltonian cycle. In [6], Faudree, Gould, Jacobson and Lesniak consider the problem of finding triples of graphs G₁, G₂, G₃, none of which is a $K_{1,s}$, s ≥ 3 such that G₁, G₂, G₃-free graphs of sufficiently large order contain a hamiltonian cycle. In this paper, a characterization will be given of all triples G₁, G₂, G₃ with none being $K_{1,3}$, such that all G₁G₂G₃-free graphs are hamiltonian. This result, together with the triples given by Brousek, completely characterize the forbidden triples G₁, G₂, G₃ such that all G₁G₂G₃-free graphs are hamiltonian.
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ć.