On the Size‐Ramsey Number of Hypergraphs

The size‐Ramsey number of a graph G is the minimum number of edges in a graph H such that every 2‐edge‐coloring of H yields a monochromatic copy of G. Size‐Ramsey numbers of graphs have been studied for almost 40 years with particular focus on the case of trees and bounded degree graphs. We initiate the study of size‐Ramsey numbers for k‐uniform hypergraphs. Analogous to the graph case, we consider the size‐Ramsey number of cliques, paths, trees, and bounded degree hypergraphs. Our results suggest that size‐Ramsey numbers for hypergraphs are extremely difficult to determine, and many open problems remain.     

Hamiltonian properties of locally connected graphs with bounded vertex degree

We consider the existence of Hamiltonian cycles for the locally connected graphs with a bounded vertex degree. For a graph G, let Δ(G) and δ(G) denote the maximum and minimum vertex degrees, respectively. We explicitly describe all connected, locally connected graphs with Δ(G)?4. We show that every connected, locally connected graph with Δ(G)=5 and δ(G)?3 is fully cycle extendable which extends the results of Kikust [P.B. Kikust, The existence of the Hamiltonian circuit in a regular graph of degree 5, Latvian Math. Annual 16 (1975) 33-38] and Hendry [G.R.T. Hendry, A strengthening of Kikust’s theorem, J. Graph Theory 13 (1989) 257-260] on full cycle extendability of the connected, locally connected graphs with the maximum vertex degree bounded by 5. Furthermore, we prove that problem Hamilton Cycle for the locally connected graphs with Δ(G)?7 is NP-complete.     

Ramsey numbers of sparse hypergraphs

Chvátal, Rödl, Szemerédi and Trotter [V. Chvátal, V. Rödl, E. Szemerédi and W.T. Trotter, The Ramsey number of a graph with a bounded maximum degree, J. Combinatorial Theory B 34 (1983), 239–243] proved that the Ramsey numbers of graphs of bounded maximum degree are linear in their order. In [O. Cooley, N. Fountoulakis, D. Kühn and D. Osthus, 3-uniform hypergraphs of bounded degree have linear Ramsey numbers, submitted] and [B. Nagle, S. Olsen, V. Rödl and M. Schacht, On the Ramsey number of sparse 3-graphs, preprint] the same result was proved for 3-uniform hypergraphs. In [O. Cooley, N. Fountoulakis, D. Kühn and D. Osthus, Embeddings and Ramsey numbers of sparse k-uniform hypergraphs, submitted] we extended this result to k-uniform hypergraphs for any integer $k\ge 3$. As in the 3-uniform case, the main new tool which we proved and used is an embedding lemma for k-uniform hypergraphs of bounded maximum degree into suitable k-uniform ‘quasi-random’ hypergraphs.     

The Ramsey number of a graph with bounded maximum degree

The Ramsey number of a graph G is the least number t for which it is true that whenever the edges of the complete graph on t vertices are colored in an arbitrary fashion using two colors, say red and blue, then it is always the case that either the red subgraph contains G or the blue subgraph contains G. A conjecture of P. Erdös and S. Burr is settled in the affirmative by proving that for each d ≥ 1, there exists a constant c so that if G is any graph on n vertices with maximum degree d, then the Ramsey number of G is at most cn.     

Linear Ramsey numbers of sparse graphs

The Ramsey number R(G₁,G₂) of two graphs G₁ and G₂ is the least integer p so that either a graph G of order p contains a copy of G₁ or its complement G^c contains a copy of G₂. In 1973, Burr and Erd?s offered a total of $25 for settling the conjecture that there is a constant c = c(d) so that R(G,G)≤ c|V(G)| for all d‐degenerate graphs G, i.e., the Ramsey numbers grow linearly for d‐degenerate graphs. We show in this paper that the Ramsey numbers grow linearly for degenerate graphs versus some sparser graphs, arrangeable graphs, and crowns for example. This implies that the Ramsey numbers grow linearly for degenerate graphs versus graphs with bounded maximum degree, planar graphs, or graphs without containing any topological minor of a fixed clique, etc. © 2005 Wiley Periodicals, Inc. J Graph Theory     

Planar graphs with maximum degree 8 and without intersecting chordal 4-cycles are 9-totally colorable

The minimum number of colors needed to properly color the vertices and edges of a graph G is called the total chromatic number of G and denoted by χ’’ (G). It is shown that if a planar graph G has maximum degree Δ≥9, then χ’’ (G) = Δ + 1. In this paper, we prove that if G is a planar graph with maximum degree 8 and without intersecting chordal 4-cycles, then χ ’’(G) = 9.     

On upper domination Ramsey numbers for graphs

The classical Ramsey number r(m,n) can be defined as the smallest integer p such that in every two-coloring (R,B) of the edges of K_p, β(B)⩾m or β(R)⩾n, where β(G) denotes the independence number of a graph G. We define the upper domination Ramsey number u(m,n) as the smallest integer p such that in every two-coloring (R,B) of the edges of K_p, Γ(B)⩾m or Γ(R)⩾n, where Γ(G) is the maximum cardinality of a minimal dominating set of a graph G. The mixed domination Ramsey number v(m,n) is defined to be the smallest integer p such that in every two-coloring (R,B) of the edges of K_p, Γ(B)⩾m or β(R)⩾n. Since β(G)⩽Γ(G) for every graph G, u(m,n)⩽v(m,n)⩽r(m,n). We develop techniques to obtain upper bounds for upper domination Ramsey numbers of the form u(3,n) and mixed domination Ramsey numbers of the form v(3,n). We show that u(3,3)=v(3,3)=6, u(3,4)=8, v(3,4)=9, u(3,5)=v(3,5)=12 and u(3,6)=v(3,6)=15.     

On matching and total domination in graphs

A set M of edges of a graph G is a matching if no two edges in M are incident to the same vertex. A set S of vertices in G is a total dominating set of G if every vertex of G is adjacent to some vertex in S. The matching number is the maximum cardinality of a matching of G, while the total domination number of G is the minimum cardinality of a total dominating set of G. In this paper, we investigate the relationships between the matching and total domination number of a graph. We observe that the total domination number of every claw-free graph with minimum degree at least three is bounded above by its matching number, and we show that every k-regular graph with k?3 has total domination number at most its matching number. In general, we show that no minimum degree is sufficient to guarantee that the matching number and total domination number are comparable.     

On maximum planar induced subgraphs

The nonplanar vertex deletion or vertex deletion vd(G) of a graph G is the smallest nonnegative integer k, such that the removal of k vertices from G produces a planar graph G^′. In this case G^′ is said to be a maximum planar induced subgraph of G. We solve a problem proposed by Yannakakis: find the threshold for the maximum degree of a graph G such that, given a graph G and a nonnegative integer k, to decide whether vd(G)?k is NP-complete. We prove that it is NP-complete to decide whether a maximum degree 3 graph G and a nonnegative integer k satisfy vd(G)?k. We prove that unless P=NP there is no polynomial-time approximation algorithm with fixed ratio to compute the size of a maximum planar induced subgraph for graphs in general. We prove that it is Max SNP-hard to compute vd(G) when restricted to a cubic input G. Finally, we exhibit a polynomial-time -approximation algorithm for finding a maximum planar induced subgraph of a maximum degree 3 graph.     

On two problems in graph Ramsey theory

We study two classical problems in graph Ramsey theory, that of determining the Ramsey number of bounded-degree graphs and that of estimating the induced Ramsey number for a graph with a given number of vertices. The Ramsey number r(H) of a graph H is the least positive integer N such that every two-coloring of the edges of the complete graph K _N contains a monochromatic copy of H. A famous result of Chváatal, Rödl, Szemerédi and Trotter states that there exists a constant c(Δ) such that r(H) ≤ c(Δ)n for every graph H with n vertices and maximum degree Δ. The important open question is to determine the constant c(Δ). The best results, both due to Graham, Rödl and Ruciński, state that there are positive constants c and c′ such that $2^{c'\Delta } \leqslant c(\Delta ) \leqslant ^{c\Delta \log ^2 \Delta }$ . We improve this upper bound, showing that there is a constant c for which c(Δ) ≤ 2 ^cΔlogΔ . The induced Ramsey number r _ind (H) of a graph H is the least positive integer N for which there exists a graph G on N vertices such that every two-coloring of the edges of G contains an induced monochromatic copy of H. Erd?s conjectured the existence of a constant c such that, for any graph H on n vertices, r _ind (H) ≤ 2 ^cnlogn . We move a step closer to proving this conjecture, showing that r _ind (H) ≤ 2 ^cnlogn . This improves upon an earlier result of Kohayakawa, Prömel and Rödl by a factor of logn in the exponent.