BZPEERSource author record
Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.
Catalog footprint
Published work
Aharoni and Howard conjectured that, for positive integers n,k,t with n≥k and n≥t, if F1,…,Ft⊆(k[n]) such that ∣Fi∣>(kn)−(kn−t+1) for i∈[t] then there exist ei∈Fi for i∈[t] such that e1,…,et are pairwise disjoint. Huang, Loh, and Sudakov proved this conjecture for t<n/(3k2). In this paper, we show that this conjecture holds for t≤n/(2k) and n sufficiently large.
As a natural extension of the Four Color Theorem, Hajós conjectured that graphs containing no K5-subdivision are 4-colorable. Any possible counterexample to this conjecture with minimum number of vertices is called a {\it Hajós graph}. Previous results show that Hajós graphs are 4-connected but not 5-connected. A k-separation in a graph G is a pair (G1,G2) of edge-disjoint subgraphs of G such that ∣V(G1∩G2)∣=k, G=G1∪G2, and Gi⊆G3−i for i=1,2. In this paper, we show that Hajós graphs do not admit a 4-separation (G1,G2) such that ∣V(G1)∣≥6 and G1 can be drawn in the plane with no edge crossings and all vertices in V(G1∩G2) incident with a common face. This is a step in our attempt to reduce Hajós' conjecture to the Four Color Theorem.
Tutte proved that every 4-connected planar graph contains a Hamilton cycle, but there are 3-connected n-vertex planar graphs whose longest cycles have length Θ(nlog32). On the other hand, Jackson and Wormald in 1992 proved that an essentially 4-connected n-vertex planar graph contains a cycle of length at least (2n+4)/5, which was recently improved to 5(n+2)/8 by Fabrici {\it et al}. In this paper, we improve this bound to ⌈(2n+6)/3⌉ for n≥6, which is best possible, by proving a quantitative version of a result of Thomassen on Tutte paths.
Kühn, Osthus, and Treglown and, independently, Khan proved that if H is a 3-uniform hypergraph with n vertices such that n∈3Z and large, and δ1(H)>(2n−1)−(22n/3), then H contains a perfect matching. In this paper, we show that for n∈3Z sufficiently large, if F1,…,Fn/3 are 3-uniform hypergrapghs with a common vertex set and δ1(Fi)>(2n−1)−(22n/3) for i∈[n/3], then {F1,…,Fn/3} admits a rainbow matching, i.e., a matching consisting of one edge from each Fi. This is done by converting the rainbow matching problem to a perfect matching problem in a special class of uniform hypergraphs.
A graph G is k-ordered if for any distinct vertices v1,v2,…,vk∈V(G), it has a cycle through v1,v2,…,vk in order. Let f(k) denote the minimum integer so that every f(k)-connected graph is k-ordered. The first non-trivial case of determining f(k) is when k=4, where the previously best known bounds are 7≤f(4)≤40. We prove that in fact f(4)=7.
Akiyama and Watanabe conjectured that every simple planar bipartite graph on n vertices contains an induced forest on at least 5n/8 vertices. We apply the discharging method to show that every simple bipartite planar graph on n vertices contains an induced forest on at least ⌈(4n+3)/7⌉ vertices.
For any posotive integer m, let [m]:={1,…,m}. Let n,k,t be positive integers. Aharoni and Howard conjectured that if, for i∈[t], $\mathcal{F}_i\subset[n]^k:= \{(a_1,\ldots,a_k): a_j\in [n] \mbox{ for } j\in [k]\}$ and ∣Fi∣>(t−1)nk−1, then there exist M⊆[n]k such that ∣M∣=t and ∣M∩Fi∣=1 for i∈[t] We show that this conjecture holds when n≥3(k−1)(t−1). Let n,t,k1≥k2≥…≥kt be positive integers. Huang, Loh and Sudakov asked for the maximum Πi=1t∣Ri∣ over all R={R1,…,Rt} such that each Ri is a collection of ki-subsets of [n] for which there does not exist a collection M of subsets of [n] such that ∣M∣=t and ∣M∩Ri∣=1 for i∈[t] %and R does not admit a rainbow matching. We show that for sufficiently large n with ∑i=1tki≤n(1−(4klnn/n)1/k), ∏i=1t∣Ri∣≤(k1−1n−1)(k2−1n−1)∏i=3t(kin). This bound is tight.
We use K4− to denote the graph obtained from K4 by removing an edge, and use TK5 to denote a subdivision of K5. Let G be a 5-connected nonplanar graph and {x1,x2,y1,y2}⊆V(G) such that G[{x1,x2, y1,y2}]≅K4− with y1y2∈/E(G). Let w1,w2,w3∈N(y2)−{x1,x2} be distinct. We show that G contains a TK5 in which y2 is not a branch vertex, or G−y2 contains K4−, or G has a special 5-separation, or G−{y2v:v∈/{w1,w2,w3,x1,x2}} contains TK5.
Let G be a 5-connected nonplanar graph and let x1,x2,y1,y2∈V(G) be distinct, such that G[{x1,x2,y1,y2}]≅K4− and y1y2∈/E(G). We show that one of the following holds: G−x1 contains K4−, or G contains a K4− in which x1 is of degree 2, or G contains a TK5 in which x1 is not a branch vertex, or {x2,y1,y2} may be chosen so that for any distinct z0,z1∈N(x1)−{x2,y1,y2}, G−{x1v:v∈/{z0,z1,x2,y1,y2}} contains TK5. This result will be used to prove the Kelmans-Seymour conjecture.
A well known theorem of Kuratowski in 1932 states that a graph is planar if, and only if, it does not contain a subdivision of K5 or K3,3. Wagner proved in 1937 that if a graph other than K5 does not contain any subdivision of K3,3 then it is planar or it admits a cut of size at most 2. Kelmans and, independently, Seymour conjectured in the 1970s that if a graph does not contain any subdivision of K5 then it is planar or it admits a cut of size at most 4. In this paper, we give a proof of the Kelmans-Seymour conjecture. We also discuss several related results and problems.
Seymour and, independently, Kelmans conjectured in the 1970s that every 5-connected nonplanar graph contains a subdivision of K5. This conjecture was proved by Ma and Yu for graphs containing K4−, and an important step in their proof is to deal with a 5-separation in the graph with a planar side. In order to establish the Kelmans-Seymour conjecture for all graphs, we need to consider 5-separations and 6-separations with less restrictive structures. The goal of this paper is to deal with special 5-separations and 6-separations, including those with an apex side. Results will be used in subsequent papers to prove the Kelmans-Seymour conjecture.
Research graph
Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.
BZPEER is loading the nearby papers, people, topics and institutions for this page.