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
In this paper, we prove that every graph with average degree at least s+t+2 has a vertex partition into two parts, such that one part has average degree at least s, and the other part has average degree at least t. This solves a conjecture of Csóka, Lo, Norin, Wu and Yepremyan.
The Hall ratio of a graph G is the maximum of |V(H)|/alpha(H) over all subgraphs H of G. Clearly, the Hall ratio of a graph is a lower bound for the fractional chromatic number. It has been asked whether conversely, the fractional chromatic number is upper bounded by a function of the Hall ratio. We answer this question in negative, by showing two results of independent interest regarding 1-subdivisions (the 1-subdivision of a graph is obtained by subdividing each edge exactly once). * For every c > 0, every graph of sufficiently large average degree contains as a subgraph the 1-subdivision of a graph of fractional chromatic number at least c. * For every d > 0, there exists a graph G of average degree at least d such that every graph whose 1-subdivision appears as a subgraph of G has Hall ratio at most 18. We also discuss the consequences of these results in the context of graph classes with bounded expansion.
We consider the problem of maximizing the number of induced copies of an oriented star Sk,ℓ in digraphs of given size, where the center of the star has out-degree k and in-degree ℓ. The case kℓ=0 was solved by Huang. Here, we asymptotically solve it for all other oriented stars with at least seven vertices.
We prove that for any constant k and any ε<1, there exist bimatrix win-lose games for which every ε-WSNE requires supports of cardinality greater than k. To do this, we provide a graph-theoretic characterization of win-lose games that possess ε-WSNE with constant cardinality supports. We then apply a result in additive number theory of Haight to construct win-lose games that do not satisfy the requirements of the characterization. These constructions disprove graph theoretic conjectures of Daskalakis, Mehta and Papadimitriou, and Myers.
For a graph H let c(H) denote the supremum of ∣E(G)∣/∣V(G)∣ taken over all non-null graphs G not containing H as a minor. We show that c(H)≤2∣V(H)∣+comp(H)−1, when H is a union of cycles, verifying conjectures of Reed and Wood, and Harvey and Wood. We derive the above result from a theorem which allows us to find two vertex disjoint subgraphs with prescribed densities in a sufficiently dense graph, which might be of independent interest.
We prove a conjecture of Ohba which says that every graph G on at most 2χ(G)+1 vertices satisfies χℓ(G)=χ(G).
Let ch(G) denote the choice number of a graph G (also called "list chromatic number" or "choosability" of G). Noel, Reed, and Wu proved the conjecture of Ohba that ch(G)=χ(G) when ∣V(G)∣≤2χ(G)+1. We extend this to a general upper bound: ch(G)≤max{χ(G),⌈(∣V(G)∣+χ(G)−1)/3⌉}. Our result is sharp for ∣V(G)∣≤3χ(G) using Ohba's examples, and it improves the best-known upper bound for ch(K4,…,4).
Interval minors of bipartite graphs were recently introduced by Jacob Fox in the study of Stanley-Wilf limits. We investigate the maximum number of edges in Kr,s-interval minor free bipartite graphs. We determine exact values when r=2 and describe the extremal graphs. For r=3, lower and upper bounds are given and the structure of K3,s-interval minor free graphs is studied.
The Hadwiger number h(G) of a graph G is the maximum size of a complete minor of G. Hadwiger's Conjecture states that h(G) >= χ(G). Since χ(G) α(G) >= |V(G)|, Hadwiger's Conjecture implies that α(G) h(G) >= |V(G)|. We show that (2 α(G) - \lceil log_t(t α(G)/2) \rceil) h(G) \geq |V(G)| where t is approximately 6.83. For graphs with α(G) \geq 14, this improves on a recent result of Kawarabayashi and Song who showed (2 α(G) - 2) h(G) >= |V(G)| when α(G) >= 3.
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.