A Proof of a Conjecture of Ohba
We prove a conjecture of Ohba which says that every graph on at most vertices satisfies .
Source author record
Bruce A. Reed
Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.
ResearcherUnclaimed source record
Catalog footprint
Research overview
4works
2topics
4close collaborators
Published work
4 publications
preprint2012arXiv
A short proof that χ can be bounded ε away from Δ+1 towards ω
In 1998 the second author proved that there is an ε>0 such that every graph satisfies χ≤⌈(1−ε)(Δ+1)+εω⌉. The first author recently proved that any graph satisfying ω>32(Δ+1) contains a stable set intersecting every maximum clique. In this note we exploit the latter result to give a much shorter, simpler proof of the former. We include, as a certificate of simplicity, an appendix that proves all intermediate results with the exception of Hall's Theorem, Brooks' Theorem, the Lovász Local Lemma, and Talagrand's Inequality.
Open access
preprint2012arXiv
Claw-free graphs, skeletal graphs, and a stronger conjecture on ω, Δ, and χ
The second author's ω, Δ, χ conjecture proposes that every graph satisties χ≤⌈21(Δ+1+ω)⌉. In this paper we prove that the conjecture holds for all claw-free graphs. Our approach uses the structure theorem of Chudnovsky and Seymour. Along the way we discuss a stronger local conjecture, and prove that it holds for claw-free graphs with a three-colourable complement. To prove our results we introduce a very useful χ-preserving reduction on homogeneous pairs of cliques, and thus restrict our view to so-called "skeletal" graphs.
Open access
preprint2011arXiv
Polynomial treewidth forces a large grid-like-minor
Robertson and Seymour proved that every graph with sufficiently large treewidth contains a large grid minor. However, the best known bound on the treewidth that forces an ℓ×ℓ grid minor is exponential in ℓ. It is unknown whether polynomial treewidth suffices. We prove a result in this direction. A \emph{grid-like-minor of order} ℓ in a graph G is a set of paths in G whose intersection graph is bipartite and contains a Kℓ-minor. For example, the rows and columns of the ℓ×ℓ grid are a grid-like-minor of order ℓ+1. We prove that polynomial treewidth forces a large grid-like-minor. In particular, every graph with treewidth at least cℓ4logℓ has a grid-like-minor of order ℓ. As an application of this result, we prove that the cartesian product G□K2 contains a Kℓ-minor whenever G has treewidth at least cℓ4logℓ.
Open access
Research graph
See the researcher in context
Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.
Building this map preview
BZPEER is loading the nearby papers, people, topics and institutions for this page.