An official website of the United States government
Abstract Let be chosen independently and uniformly at random from the unit ‐dimensional cube . Let be given and let . The random geometric graph has vertex set and an edge whenever . We show that if each edge of is colored independently from one of colors and has the smallest value such that has minimum degree at least two, then contains a rainbow Hamilton cycle asymptotically almost surely.
more »
« less
Double Vizing fans in critical class two graphs
Abstract Let be a simple graph and be the chromatic index of . We call a ‐critical graphif for every edge of , where is maximum degree of . Let be an edge of ‐critical graph and be an (proper) edge ‐coloring of . Ane‐fanis a sequence of alternating vertices and distinct edges such that edge is incident with or , is another endvertex of and is missing at a vertex before for each with . In this paper, we prove that if , where and denote the degrees of vertices and , respectively, then colors missing at different vertices of are distinct. Clearly, a Vizing fan is an ‐fan with the restricting that all edges being incident with one fixed endvertex of edge . This result gives a common generalization of several recently developed new results on multifan, double fan, Kierstead path of four vertices, and broom. By treating some colors of edges incident with vertices of low degrees as missing colors, Kostochka and Stiebitz introduced ‐fan. In this paper, we also generalize the ‐fan from centered at one vertex to one edge.
more »
« less
- PAR ID:
- 10506016
- Publisher / Repository:
- John Wiley
- Date Published:
- Journal Name:
- Journal of Graph Theory
- Volume:
- 103
- Issue:
- 1
- ISSN:
- 0364-9024
- Page Range / eLocation ID:
- 48 to 65
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Abstract Let be a ‐regular graph on vertices. Frieze, Gould, Karoński, and Pfender began the study of the following random spanning subgraph model . Assign independently to each vertex of a uniform random number , and an edge of is an edge of if and only if . Addressing a problem of Alon and Wei, we prove that if , then with high probability, for each nonnegative integer , there are vertices of degree in .more » « less
-
One of the most intruguing conjectures in extremal graph theory is the conjecture of Erdős and Sós from 1962, which asserts that every $$n$$-vertex graph with more than $$\frac{k-1}{2}n$$ edges contains any $$k$$-edge tree as a subgraph. Kalai proposed a generalization of this conjecture to hypergraphs. To explain the generalization, we need to define the concept of a tight tree in an $$r$$-uniform hypergraph, i.e., a hypergraph where each edge contains $$r$$ vertices. A tight tree is an $$r$$-uniform hypergraph such that there is an ordering $$v_1,\ldots,v_n$$ of its its vertices with the following property: the vertices $$v_1,\ldots,v_r$$ form an edge and for every $i>r$, there is a single edge $$e$$ containing the vertex $$v_i$$ and $r-1$ of the vertices $$v_1,\ldots,v_{i-1}$$, and $$e\setminus\{v_i\}$$ is a subset of one of the edges consisting only of vertices from $$v_1,\ldots,v_{i-1}$$. The conjecture of Kalai asserts that every $$n$$-vertex $$r$$-uniform hypergraph with more than $$\frac{k-1}{r}\binom{n}{r-1}$$ edges contains every $$k$$-edge tight tree as a subhypergraph. The recent breakthrough results on the existence of combinatorial designs by Keevash and by Glock, Kühn, Lo and Osthus show that this conjecture, if true, would be tight for infinitely many values of $$n$$ for every $$r$$ and $$k$$.The article deals with the special case of the conjecture when the sought tight tree is a path, i.e., the edges are the $$r$$-tuples of consecutive vertices in the above ordering. The case $r=2$ is the famous Erdős-Gallai theorem on the existence of paths in graphs. The case $r=3$ and $k=4$ follows from an earlier work of the authors on the conjecture of Kalai. The main result of the article is the first non-trivial upper bound valid for all $$r$$ and $$k$$. The proof is based on techniques developed for a closely related problem where a hypergraph comes with a geometric structure: the vertices are points in the plane in a strictly convex position and the sought path has to zigzag beetwen the vertices.more » « less
-
Fix k>0, and let G be a graph, with vertex set partitioned into k subsets (`blocks') of approximately equal size. An induced subgraph of G is transversal (with respect to this partition) if it has exactly one vertex in each block (and therefore it has exactly k vertices). A pure pair in G is a pair X,Y of disjoint subsets of V(G) such that either all edges between X,Y are present or none are; and in the present context we are interested in pure pairs (X,Y) where each of X,Y is a subset of one of the blocks, and not the same block. This paper collects several results and open questions concerning how large a pure pair must be present if various types of transversal subgraphs are excluded.more » « less
-
Abstract Let denote the complete 3‐uniform hypergraph on vertices and the 3‐uniform hypergraph on vertices consisting of all edges incident to a given vertex. Whereas many hypergraph Ramsey numbers grow either at most polynomially or at least exponentially, we show that the off‐diagonal Ramsey number exhibits an unusual intermediate growth rate, namely,for some positive constants and . The proof of these bounds brings in a novel Ramsey problem on grid graphs which may be of independent interest: what is the minimum such that any 2‐edge‐coloring of the Cartesian product contains either a red rectangle or a blue ?more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Journal Article:
- https://doi.org/10.1002/jgt.22903
