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

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

Wyniki wyszukiwania

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

A note on the Ramsey number and the planar Ramsey number for C₄ and complete graphs

100%
Bielak H.
Discussiones Mathematicae Graph Theory
|
1999
|
tom 19
|
nr 2
135-142
EN
We give a lower bound for the Ramsey number and the planar Ramsey number for C₄ and complete graphs. We prove that the Ramsey number for C₄ and K₇ is 21 or 22. Moreover we prove that the planar Ramsey number for C₄ and K₆ is equal to 17.
2
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Multicolor Ramsey numbers for paths and cycles

100%
Dzido T.
Discussiones Mathematicae Graph Theory
|
2005
|
tom 25
|
nr 1-2
57-65
EN
For given graphs G₁,G₂,...,Gₖ, k ≥ 2, the multicolor Ramsey number R(G₁,G₂,...,Gₖ) is the smallest integer n such that if we arbitrarily color the edges of the complete graph on n vertices with k colors, then it is always a monochromatic copy of some $G_i$, for 1 ≤ i ≤ k. We give a lower bound for k-color Ramsey number R(Cₘ,Cₘ,...,Cₘ), where m ≥ 8 is even and Cₘ is the cycle on m vertices. In addition, we provide exact values for Ramsey numbers R(P₃,Cₘ,Cₚ), where P₃ is the path on 3 vertices, and several values for R(Pₗ,Pₘ,Cₚ), where l,m,p ≥ 2. In this paper we present new results in this field as well as some interesting conjectures.
3
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

The Ramsey numbers for some subgraphs of generalized wheels versus cycles and paths

80%
Bielak H., Dąbrowska K.
Annales Universitatis Mariae Curie-Skłodowska, sectio A – Mathematica
|
2015
|
tom 69
|
nr 2
EN
The Ramsey number \(R(G, H)\) for a pair of graphs \(G\) and \(H\) is defined as the smallest integer \(n\) such that, for any graph \(F\) on \(n\) vertices, either \(F\) contains \(G\) or \(\overline{F}\) contains \(H\) as a subgraph, where \(\overline{F}\) denotes the complement of \(F\). We study Ramsey numbers for some subgraphs of generalized wheels versus cycles and paths and determine these numbers for some cases. We extend many known results studied in [5, 14, 18, 19, 20]. In particular we count the numbers \(R(K_1+L_n, P_m)\) and \(R(K_1+L_n, C_m)\) for some integers \(m\), \(n\), where \(L_n\) is a linear forest of order \(n\) with at least one edge.
4
Content available remote

The ramsey number for theta graph versus a clique of order three and four

80%
Bataineh M. S. A., Jaradat M. M. M., Bateeha M. S.
Discussiones Mathematicae Graph Theory
|
2014
|
tom 34
|
nr 2
223-232
EN
For any two graphs F1 and F2, the graph Ramsey number r(F1, F2) is the smallest positive integer N with the property that every graph on at least N vertices contains F1 or its complement contains F2 as a subgraph. In this paper, we consider the Ramsey numbers for theta-complete graphs. We determine r(θn,Km) for m = 2, 3, 4 and n > m. More specifically, we establish that r(θn,Km) = (n − 1)(m − 1) + 1 for m = 3, 4 and n > m
5
Content available remote

Critical Graphs for R(Pn, Pm) and the Star-Critical Ramsey Number for Paths

80%
Hook J.
Discussiones Mathematicae Graph Theory
|
2015
|
tom 35
|
nr 4
689-701
EN
The graph Ramsey number R(G,H) is the smallest integer r such that every 2-coloring of the edges of Kr contains either a red copy of G or a blue copy of H. The star-critical Ramsey number r∗(G,H) is the smallest integer k such that every 2-coloring of the edges of Kr − K1,r−1−k contains either a red copy of G or a blue copy of H. We will classify the critical graphs, 2-colorings of the complete graph on R(G,H) − 1 vertices with no red G or blue H, for the path-path Ramsey number. This classification will be used in the proof of r∗(Pn, Pm).
6
Content available remote

On Monochromatic Subgraphs of Edge-Colored Complete Graphs

80%
Andrews E., Fujie F., Kolasinski K., Lumduanhom C., Yusko A.
Discussiones Mathematicae Graph Theory
|
2014
|
tom 34
|
nr 1
5-22
EN
In a red-blue coloring of a nonempty graph, every edge is colored red or blue. If the resulting edge-colored graph contains a nonempty subgraph G without isolated vertices every edge of which is colored the same, then G is said to be monochromatic. For two nonempty graphs G and H without isolated vertices, the mono- chromatic Ramsey number mr(G,H) of G and H is the minimum integer n such that every red-blue coloring of Kn results in a monochromatic G or a monochromatic H. Thus, the standard Ramsey number of G and H is bounded below by mr(G,H). The monochromatic Ramsey numbers of graphs belonging to some common classes of graphs are studied. We also investigate another concept closely related to the standard Ram- sey numbers and monochromatic Ramsey numbers of graphs. For a fixed integer n ≥ 3, consider a nonempty subgraph G of order at most n con- taining no isolated vertices. Then G is a common monochromatic subgraph of Kn if every red-blue coloring of Kn results in a monochromatic copy of G. Furthermore, G is a maximal common monochromatic subgraph of Kn if G is a common monochromatic subgraph of Kn that is not a proper sub- graph of any common monochromatic subgraph of Kn. Let S(n) and S*(n) be the sets of common monochromatic subgraphs and maximal common monochromatic subgraphs of Kn, respectively. Thus, G ∈ S(n) if and only if R(G,G) = mr(G,G) ≤ n. We determine the sets S(n) and S*(n) for 3 ≤ n ≤ 8.
7
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

The Chvátal-Erdős condition and 2-factors with a specified number of components

80%
Chen G., Gould R., Kawarabayashi K.-i., Ota K., Saito A., Schiermeyer I.
Discussiones Mathematicae Graph Theory
|
2007
|
tom 27
|
nr 3
401-407
EN
Let G be a 2-connected graph of order n satisfying α(G) = a ≤ κ(G), where α(G) and κ(G) are the independence number and the connectivity of G, respectively, and let r(m,n) denote the Ramsey number. The well-known Chvátal-Erdös Theorem states that G has a hamiltonian cycle. In this paper, we extend this theorem, and prove that G has a 2-factor with a specified number of components if n is sufficiently large. More precisely, we prove that (1) if n ≥ k·r(a+4, a+1), then G has a 2-factor with k components, and (2) if n ≥ r(2a+3, a+1)+3(k-1), then G has a 2-factor with k components such that all components but one have order three.
8
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Multicolor Ramsey numbers for some paths and cycles

80%
Bielak H.
Discussiones Mathematicae Graph Theory
|
2009
|
tom 29
|
nr 2
209-218
EN
We give the multicolor Ramsey number for some graphs with a path or a cycle in the given sequence, generalizing a results of Faudree and Schelp [4], and Dzido, Kubale and Piwakowski [2,3].
9
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Planar Ramsey numbers

80%
Gorgol I.
Discussiones Mathematicae Graph Theory
|
2005
|
tom 25
|
nr 1-2
45-50
EN
The planar Ramsey number PR(G,H) is defined as the smallest integer n for which any 2-colouring of edges of Kₙ with red and blue, where red edges induce a planar graph, leads to either a red copy of G, or a blue H. In this note we study the weak induced version of the planar Ramsey number in the case when the second graph is complete.
10
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Structural results on maximal k-degenerate graphs

71%
Bickle A.
Discussiones Mathematicae Graph Theory
|
2012
|
tom 32
|
nr 4
659-676
EN
A graph is k-degenerate if its vertices can be successively deleted so that when deleted, each has degree at most k. These graphs were introduced by Lick and White in 1970 and have been studied in several subsequent papers. We present sharp bounds on the diameter of maximal k-degenerate graphs and characterize the extremal graphs for the upper bound. We present a simple characterization of the degree sequences of these graphs and consider related results. Considering edge coloring, we conjecture that a maximal k-degenerate graph is class two if and only if it is overfull, and prove this in some special cases. We present some results on decompositions and arboricity of maximal k-degenerate graphs and provide two characterizations of the subclass of k-trees as maximal k-degenerate graphs. Finally, we define and prove a formula for the Ramsey core numbers.
11
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Generalized ramsey theory and decomposable properties of graphs

61%
Burr S., Jacobson M., Mihók P., Semanišin G.
Discussiones Mathematicae Graph Theory
|
1999
|
tom 19
|
nr 2
199-217
EN
In this paper we translate Ramsey-type problems into the language of decomposable hereditary properties of graphs. We prove a distributive law for reducible and decomposable properties of graphs. Using it we establish some values of graph theoretical invariants of decomposable properties and show their correspondence to generalized Ramsey numbers.
12
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Three edge-coloring conjectures

61%
Schelp R.
Discussiones Mathematicae Graph Theory
|
2002
|
tom 22
|
nr 1
173-182
EN
The focus of this article is on three of the author's open conjectures. The article itself surveys results relating to the conjectures and shows where the conjectures are known to hold.
13
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Some applications of pq-groups in graph theory

61%
Exoo G.
Discussiones Mathematicae Graph Theory
|
2004
|
tom 24
|
nr 1
109-114
EN
We describe some new applications of nonabelian pq-groups to construction problems in Graph Theory. The constructions include the smallest known trivalent graph of girth 17, the smallest known regular graphs of girth five for several degrees, along with four edge colorings of complete graphs that improve lower bounds on classical Ramsey numbers.
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ć.