93 research outputs found
A generalized Ramsey problem
No full textAbstractLet f(n) be the minimum number such that there is a proper edge-coloring of Kn with f(n) colors with no path or cycle of 4 edges using one or two colors. It is shown that [(1+5)/2]n−3⩽f(n)⩽2n1+c/logn for a positive constants c. This improves the existent bounds on the variant of the Ramsey number f(n,5,9) studied by Erdős and Gyárfás
On the structure of graphs with forbidden induced substructures
No full textOne of the central goals in extremal combinatorics is to understand how the global structure of a combinatorial object, e.g. a graph, hypergraph or set system, is affected by local constraints.
In this thesis we are concerned with structural properties of graphs and hypergraphs which locally do not look like some type of forbidden induced pattern. Patterns can be single subgraphs, families of subgraphs, or in the multicolour version colourings or families of colourings of subgraphs.
Erdős and Szekeres\u27s quantitative version of Ramsey\u27s theorem asserts that in every -edge-colouring of the complete graph on vertices there is a monochromatic clique on at least vertices. The famous Erdős-Hajnal conjecture asserts that forbidding fixed colourings on subgraphs ensures much larger monochromatic cliques. The conjecture is open in general, though a few partial results are known. The first part of this thesis will be concerned with different variants of this conjecture: A bipartite variant, a multicolour variant, and an order-size variant for hypergraphs.
In the second part of this thesis we focus more on order-size pairs; an order-size pair is the family consisting of all graphs of order and size , i.e. on vertices with edges. We consider order-size pairs in different settings: The graph setting, the bipartite setting and the hypergraph setting. In all these settings we investigate the existence of absolutely avoidable pairs, i.e. fixed pairs that are avoided by all order-size pairs with sufficiently large order, and also forcing densities of order-size pairs , i.e. for approaching infinity, the limit superior of the fraction of all possible sizes , such that the order-size pair does not avoid the pair
List-coloring and sum-list-coloring problems on graphs
No full textGraph coloring is a well-known and well-studied area of graph theory that has many applications. In this dissertation, we look at two generalizations of graph coloring known as list-coloring and sum-list-coloring. In both of these types of colorings, one seeks to first assign palettes of colors to vertices and then choose a color from the corresponding palette for each vertex so that a proper coloring is obtained.
A celebrated result of Thomassen states that every planar graph can be properly colored from any arbitrarily assigned palettes of five colors. This result is known as 5-list-colorability of planar graphs. Albertson asked whether Thomassen's theorem can be extended by precoloring some vertices which are at a large enough distance apart. Hutchinson asked whether Thomassen's theorem can be extended by allowing certain vertices to have palettes of size less than five assigned to them. In this dissertation, we explore both of these questions and answer them in the affirmative for various classes of graphs.
We also provide a catalog of small configurations with palettes of different prescribed sizes and determine whether or not they can always be colored from palettes of such sizes. These small configurations can be useful in reducing certain planar graphs to obtain more information about their structure.
Additionally, we look at the newer notion of sum-list-coloring where the sum choice number is the parameter of interest. In sum-list-coloring, we seek to minimize the sum of varying sizes of palettes of colors assigned the vertices of a graph. We compute the sum choice number for all graphs on at most five vertices, present some general results about sum-list-coloring, and determine the sum choice number for certain graphs made up of cycles.</p
On multiple coverings of the infinite rectangular grid with balls of constant radius
No full textAbstractWe consider the coverings of graphs with balls of constant radius satisfying special multiplicity condition. A (t,i,j)-cover of a graph G=(V,E) is a subset S of vertices, such that every element of S belongs to exactly i balls of radius t centered at elements of S and every element of V⧹S belongs to exactly j balls of radius t centered at elements of S. For the infinite rectangular grid, we show that in any (t,i,j)-cover, i and j differ by at most t+2 except for one degenerate case. Furthermore, for i and j satisfying |i−j|>4 we show that all (t,i,j)-covers are the unions of the diagonals periodically located in the grid. Also, we give the description of all (1,i,j)-covers
A class of graphs of zero Tur\'an density in a hypercube
No full textA graph is cubical if it is a subgraph of a hypercube. For a cubical graph
and a hypercube , is the largest number of edges in an
-free subgraph of . If is at least a positive proportion
of the number of edges in , is said to have a positive Tur\'an density
in a hypercube or simply a positive Tur\'an density; otherwise it has a zero
Tur\'an density. Determining and even identifying whether has
a positive or a zero Tur\'an density remains a widely open question for general
. By relating extremal numbers in a hypercube and certain corresponding
hypergraphs, Conlon found a large class of cubical graphs, ones having
so-called partite representation, that have a zero Tur\'an density. He raised a
question whether this gives a characterisation, i.e., whether a cubical graph
has zero Tur\'an density if and only if it has partite representation. Here, we
show that, as suspected by Conlon, this is not the case. We give an example of
a class of cubical graphs which have no partite representation, but on the
other hand, have a zero Tur\'an density. In addition, we show that any graph
whose every block has partite representation has a zero Tur\'an density in a
hypercube
- …
