# Search results for: Andrzej Ruciński

Journal of Graph Theory > 98 > 3 > 460 - 498

*for all*$n$. We also establish the second‐ and third‐order Turán numbers and use them to compute the corresponding Ramsey numbers for up to four colors.

Journal of Graph Theory > 98 > 2 > 255 - 284

Random Structures & Algorithms > 56 > 1 > 122 - 141

*k*≥ 1 and sufficiently large

*n*already the minimum degree $\delta \left(G\right)\ge \frac{k}{k+1}n$ for an

*n*‐vertex graph

*G*alone suffices to ensure the existence of a

*k*th power of a...

Discussiones Mathematicae Graph Theory > 2017 > 37 > 3 > 755-776

Annals of Combinatorics > 2017 > 21 > 1 > 95-117

Discrete Mathematics > 2017 > 340 > 2 > 107-118

Journal of Combinatorial Theory, Series B > 2017 > 122 > C > 719-740

Combinatorica > 2017 > 37 > 4 > 767-784

*k*and

*r*, the Folkman number

*f*(

*k*;

*r*) is the smallest number of vertices in a graph

*G*which contains no clique on

*k*+1 vertices, yet for every partition of its edges into

*r*parts, some part contains a clique of order

*k*. The existence (finiteness) of Folkman numbers was established by Folkman (1970) for

*r*=2 and by Nešetřil and Rödl (1976) for arbitrary

*r*, but these proofs led to very...

Enhanced Methods in Computer Security, Biometric and Artificial Intelligence Systems > Information Technology Security > 113-124

Lecture Notes in Computer Science > Mathematical Foundations of Computer Science 2005 > Invited Lectures > 52-56

*n*-vertex graph to be hamiltonian, and thus, for

*n*even, to have a perfect matching, is that the minimum degree is at least

*n*/2. Moreover, there are obvious counterexamples showing that this is best...

Lecture Notes in Computer Science > Randomization and Approximation Techniques in Computer Science > Regular Papers > 25-34

*H*as a spanning subgraph of an e-regular graph

*G*. The first proof given by Komlós, Sárközy, and Szemerédi was based on a probabilistic argument [8]. Subsequently, they derandomized their approach to provide an algorithmic embedding in [9]....

Lecture Notes in Computer Science > Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques > Contributed Talks of RANDOM > 170-180

*G*is $$ \mathcal{H} $$-universal if, for each

*H*∈ $$ \mathcal{H} $$, the graph

*G*contains a subgraph isomorphic to

*H*. Let $$ \mathcal{H} $$ (

*k, n*) denote the family of graphs on

*n*vertices with maximum degree at most

*k*. For each fixed

*k*and each

*n*sufficiently large, we explicitly construct an $$ \mathcal{H} $$ (

*k, n*)-universal graph

*Γ*(

*k, n*)...

*k*-uniform hypergraphs. Some of these problems are known to be notoriously hard. There is also a renewed interest recently in the very special cases of them. One of the goals of this paper is to shed some light on the tractability barriers for those problems. It...

Bolyai Society Mathematical Studies > An Irregular Mind > 561-590

Random Structures & Algorithms > 46 > 2 > 274 - 299

*H, G*) of

*n*‐vertex graphs, searches for an embedding of

*H*into

*G*. If

*H*has bounded maximum degree and

*G*is suitably dense and pseudorandom, then the algorithm succeeds with high probability. Our algorithm proves that, for every integer $d\ge 3$ and a large enough constant

*C*=

*C*

_{d}, as $n\to \infty $, asymptotically almost all graphs with...

Discussiones Mathematicae Graph Theory > 2014 > 34 > 2 > 361-381