Source author record

Paul Seymour

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.CO Discrete Mathematics Data Structures and Algorithms math.GT

Catalog footprint

Research overview

45works

4topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2023arXiv

Induced paths in graphs without anticomplete cycles

Let us say a graph is $s\mathcal{O}$ -free, where $s\ge 1$ is an integer, if there do not exist $s$ cycles of the graph that are pairwise vertex-disjoint and have no edges joining them. The structure of such graphs, even when $s=2$ , is not well understood. For instance, until now we did not know how to test whether a graph is $2\mathcal{O}$ -free in polynomial time; and there was an open conjecture, due to Ngoc Khang Le, that $2\mathcal{O}$ -free graphs have only a polynomial number of induced paths. In this paper we prove Le's conjecture; indeed, we will show that for all $s\ge 1$ , there exists $c>0$ such that every $s\mathcal{O}$ -free graph $G$ has at most $|G|^c$ induced paths. This provides a poly-time algorithm to test if a graph is $s\mathcal{O}$ -free, for all fixed $s$ . The proof has three parts. First, there is a short and beautiful proof, due to Le, that reduces the question to proving the same thing for graphs with no cycles of length four. Second, there is a recent result of Bonamy, Bonnet, Déprés, Esperet, Geniet, Hilaire, Thomassé and Wesolek, that in every $s\mathcal{O}$ -free graph $G$ with no cycle of length four, there is a set of vertices that intersects every cycle, with size logarithmic in $|G|$ . And third, there is an argument that uses the result of Bonamy et al. to deduce the theorem. The last is the main content of this paper.

preprint2023arXiv

Polynomial bounds for chromatic number. V. Excluding a tree of radius two and a complete multipartite graph

The Gyárfás-Sumner conjecture says that for every forest $H$ and every integer $k$ , if $G$ is $H$ -free and does not contain a clique on $k$ vertices then it has bounded chromatic number. (A graph is $H$ -free if it does not contain an induced copy of $H$ .) Kierstead and Penrice proved it for trees of radius at most two, but otherwise the conjecture is known only for a few simple types of forest. More is known if we exclude a complete bipartite subgraph instead of a clique: Rödl showed that, for every forest $H$ , if $G$ is $H$ -free and does not contain $K_{t,t}$ as a subgraph then it has bounded chromatic number. In an earlier paper with Sophie Spirkl, we strengthened Rödl's result, showing that for every forest $H$ , the bound on chromatic number can be taken to be polynomial in $t$ . In this paper, we prove a related strengthening of the Kierstead-Penrice theorem, showing that for every tree $H$ of radius two and every integer $d\ge 2$ , if $G$ is $H$ -free and does not contain as a subgraph the complete $d$ -partite graph with parts of cardinality $t$ , then its chromatic number is at most polynomial in $t$ .

preprint2022arXiv

Bipartite graphs with no $K_6$ minor

A theorem of Mader shows that every graph with average degree at least eight has a $K_6$ minor, and this is false if we replace eight by any smaller constant. Replacing average degree by minimum degree seems to make little difference: we do not know whether all graphs with minimum degree at least seven have $K_6$ minors, but minimum degree six is certainly not enough. For every $c>0$ there are arbitrarily large graphs with average degree at least $8-c$ and minimum degree at least six, with no $K_6$ minor. But what if we restrict ourselves to bipartite graphs? The first statement remains true: for every $c>0$ there are arbitrarily large bipartite graphs with average degree at least $8-c$ and no $K_6$ minor. But surprisingly, going to minimum degree now makes a significant difference. We will show that every bipartite graph with minimum degree at least six has a $K_6$ minor. Indeed, it is enough that every vertex in the larger part of the bipartition has degree at least six.

preprint2022arXiv

Dense minors of graphs with independence number two

Motivated by Hadwiger's conjecture, we prove that every $n$ -vertex graph $G$ with no independent set of size three contains an $\lceil n/2\rceil$ -vertex simple minor $H$ with $0.98688 \cdot \binom{|V(H)|}{2} - o(n^2)$ edges.

preprint2022arXiv

Polynomial bounds for chromatic number VII. Disjoint holes

A hole in a graph $G$ is an induced cycle of length at least four, and a $k$ -multihole in $G$ is a set of pairwise disjoint and nonadjacent holes. It is well known that if $G$ does not contain any holes then its chromatic number is equal to its clique number. In this paper we show that, for any $k$ , if $G$ does not contain a $k$ -multihole, then its chromatic number is at most a polynomial function of its clique number. We show that the same result holds if we ask for all the holes to be odd or of length four; and if we ask for the holes to be longer than any fixed constant or of length four. This is part of a broader study of graph classes that are polynomially $χ$ -bounded.

preprint2022arXiv

Proof of a conjecture of Plummer and Zha

Say a graph $G$ is a {\em pentagraph} if every cycle has length at least five, and every induced cycle of odd length has length five. N. Robertson proposed the conjecture that the Petersen graph is the only pentagraph that is three-connected and internally 4-connected, but this was disproved by M. Plummer and X. Zha in 2014. Plummer and Zha conjectured that every 3-connected, internally 4-connected pentagraph is three-colourable. We prove this: indeed, we will prove that every pentagraph is three-colourable.

preprint2022arXiv

Strengthening Rodl's theorem

What can be said about the structure of graphs that do not contain an induced copy of some graph H? Rodl showed in the 1980s that every H-free graph has large parts that are very dense or very sparse. More precisely, let us say that a graph F on n vertices is c-restricted if either F or its complement has maximum degree at most cn. Rodl proved that for every graph H, and every c>0, every H-free graph G has a linear-sized set of vertices inducing a c-restricted graph. We strengthen Rodl's result as follows: for every graph H, and all c>0, every H-free graph can be partitioned into a bounded number of subsets inducing c-restricted graphs.

preprint2021arXiv

Erdos-Hajnal for graphs with no 5-hole

The Erdos-Hajnal conjecture says that for every graph H there exists c>0 such that every graph G not containing H as an induced subgraph has a clique or stable set of cardinality at least |G|^c. We prove that this is true when H is a cycle of length five. We also prove several further results: for instance, that if C is a cycle and H is the complement of a forest, there exists c>0 such that every graph G containing neither of C,H as an induced subgraph has a clique or stable set of cardinality at least |G|^c.

preprint2021arXiv

Pure pairs. VII. Homogeneous submatrices in 0/1-matrices with a forbidden submatrix

For integer $n>0$ , let $f(n)$ be the number of rows of the largest all-0 or all-1 square submatrix of $M$ , minimized over all $n\times n$ $0/1$ -matrices $M$ . Thus $f(n)= O(\log n)$ . But let us fix a matrix $H$ , and define $f_H(n)$ to be the same, minimized over over all $n\times n$ $0/1$ -matrices $M$ such that neither $M$ nor its complement (that is, change all $0$ 's to $1$ 's and vice versa) contains $H$ as a submatrix. It is known that $f_H(n)\ge εn^c$ , where $c, ε>0$ are constants depending on $H$ . When can we take $c=1$ ? If so, then one of $H$ and its complement must be an acyclic matrix (that is, the corresponding bipartite graph is a forest). Korandi, Pach, and Tomon conjectured the converse, that $f_H(n)$ is linear in $n$ for every acyclic matrix $H$ ; and they proved it for certain matrices $H$ with only two rows. Their conjecture remains open, but we show $f_H(n)=n^{1-o(1)}$ for every acyclic matrix $H$ ; and indeed there is a $0/1$ -submatrix that is either $Ω(n)\times n^{1-o(1)}$ or $n^{1-o(1)}\times Ω(n)$ .

preprint2020arXiv

A survey of $χ$ -boundedness

If a graph has bounded clique number, and sufficiently large chromatic number, what can we say about its induced subgraphs? András Gyárfás made a number of challenging conjectures about this in the early 1980's, which have remained open until recently; but in the last few years there has been substantial progress. This is a survey of where we are now.

preprint2020arXiv

Detecting a long even hole

For each integer $\ell \geq 4$ , we give a polynomial-time algorithm to test whether a graph contains an induced cycle with length at least $\ell$ and even

preprint2020arXiv

Detecting a long odd hole

For each integer $t\ge 5$ , we give a polynomial-time algorithm to test whether a graph contains an induced cycle with length at least $t$ and odd.

preprint2020arXiv

Even-hole-free graphs still have bisimplicial vertices

A {\em hole} in a graph is an induced subgraph which is a cycle of length at least four. A hole is called {\em even} if it has an even number of vertices. An {\em even-hole-free} graph is a graph with no even holes. A vertex of a graph is {\em bisimplicial} if the set of its neighbours is the union of two cliques. In an earlier paper \cite{bisimplicial}, Addario-Berry, Havet and Reed, with the authors, claimed to prove a conjecture of Reed, that every even-hole-free graph has a bisimplicial vertex, but we have recently been shown that the "proof" has a serious error. Here we give a proof using a different method.

preprint2020arXiv

Finding a shortest odd hole

An odd hole in a graph is a induced cycle with odd length greater than 3. In an earlier paper (with Sophie Spirkl), solving a longstanding open problem, we gave a polynomial-time algorithm to test if a graph has an odd hole. We subsequently showed that, for every t, there is a polynomial time algorithm to test whether a graph contains an odd hole of length at least t. In this paper, we give an algorithm that finds a shortest odd hole, if one exists.

preprint2020arXiv

Finding an induced path that is not a shortest path

We give a polynomial-time algorithm that, with input a graph $G$ and two vertices $u,v$ of $G$ , decides whether there is an induced $uv$ -path that is longer than the shortest $uv$ -path.

preprint2020arXiv

Holes with hats and Erdős-Hajnal

A "hole-with-hat" in a graph $G$ is an induced subgraph of $G$ that consists of a cycle of length at least four, together with one further vertex that has exactly two neighbours in the cycle, adjacent to each other, and the "house" is the smallest, on five vertices. It is not known whether there exists $ε>0$ such that every graph $G$ containing no house has a clique or stable set of cardinality at least $|G|^ε$ ; this is one of the three smallest open cases of the Erdős-Hajnal conjecture and has been the subject of much study. We prove that there exists $ε>0$ such that every graph $G$ with no hole-with-hat has a clique or stable set of cardinality at least $|G|^ε$

preprint2020arXiv

Induced subgraphs of bounded treewidth and the container method

A hole in a graph is an induced cycle of length at least 4. A hole is long if its length is at least 5. By $P_t$ we denote a path on $t$ vertices. In this paper we give polynomial-time algorithms for the following problems: the Maximum Weight Independent Set problem in long-hole-free graphs, and the Feedback Vertex Set problem in $P_5$ -free graphs. Each of the above results resolves a corresponding long-standing open problem. An extended $C_5$ is a five-vertex hole with an additional vertex adjacent to one or two consecutive vertices of the hole. Let $\mathcal{C}$ be the class of graphs excluding an extended $C_5$ and holes of length at least $6$ as induced subgraphs; $\mathcal{C}$ contains all long-hole-free graphs and all $P_5$ -free graphs. We show that, given an $n$ -vertex graph $G \in \mathcal{C}$ with vertex weights and an integer $k$ , one can in time $n^{\Oh(k)}$ find a maximum-weight induced subgraph of $G$ of treewidth less than $k$ . This implies both aforementioned results.

preprint2020arXiv

New Examples of Minimal Non-Strongly-Perfect Graphs

A graph is strongly perfect if every induced subgraph H has a stable set that meets every nonempty maximal clique of H. The characterization of strongly perfect graphs by a set of forbidden induced subgraphs is not known. Here we provide several new minimal non-strongly-perfect graphs.

preprint2020arXiv

Pure pairs. I. Trees and linear anticomplete pairs

The Erdos-Hajnal Conjecture asserts that for every graph H there is a constant c > 0 such that every graph G that does not contain H as an induced subgraph has a clique or stable set of cardinality at least |G|^c. In this paper, we prove a conjecture of Liebenau and Pilipczuk, that for every forest H there exists c > 0, such that every graph G contains either an induced copy of H, or a vertex of degree at least c|G|, or two disjoint sets of at least c|G| vertices with no edges between them. It follows that for every forest H there is c > 0 so that if G contains neither H nor its complement as an induced subgraph then there is a clique or stable set of cardinality at least |G|^c.

preprint2020arXiv

Pure pairs. II. Excluding all subdivisions of a graph

We prove for every graph H there exists a>0 such that, for every graph G with at least two vertices, if no induced subgraph of G is a subdivision of H, then either some vertex of G has at least a|G| neighbours, or there are two disjoint sets A,B of at least a|G| vertices such that no edge joins A and B. It follows that for every graph H, there exists c>0 such that for every graph G, if no induced subgraph of G or its complement is a subdivision of H, then G has a clique or stable set of cardinality at least |G|^c. This is related to the Erdos-Hajnal conjecture.

preprint2018arXiv

Clustered Colouring in Minor-Closed Classes

The "clustered chromatic number" of a class of graphs is the minimum integer $k$ such that for some integer $c$ every graph in the class is $k$ -colourable with monochromatic components of size at most $c$ . We prove that for every graph $H$ , the clustered chromatic number of the class of $H$ -minor-free graphs is tied to the tree-depth of $H$ . In particular, if $H$ is connected with tree-depth $t$ then every $H$ -minor-free graph is $(2^{t+1}-4)$ -colourable with monochromatic components of size at most $c(H)$ . This provides the first evidence for a conjecture of Ossona de Mendez, Oum and Wood (2016) about defective colouring of $H$ -minor-free graphs. If $t=3$ then we prove that 4 colours suffice, which is best possible. We also determine those minor-closed graph classes with clustered chromatic number 2. Finally, we develop a conjecture for the clustered chromatic number of an arbitrary minor-closed class.

preprint2016arXiv

Induced subgraphs of graphs with large chromatic number. III. Long holes

We prove a 1985 conjecture of Gyárfás that for all $k,\ell$ , every graph with sufficiently large chromatic number contains either a complete subgraph with $k$ vertices or an induced cycle of length at least $\ell$ .

preprint2015arXiv

Excluding A Grid Minor In Planar Digraphs

In [Directed tree-width, J. Combin. Theory Ser. B 82 (2001), 138-154] we introduced the notion of tree-width of directed graphs and presented a conjecture, formulated during discussions with Noga Alon and Bruce Reed, stating that a digraph of huge tree-width has a large "cylindrical grid" minor. Here we prove the conjecture for planar digraphs, but many steps of the proof work in general. This is an unedited and unpolished manuscript from October 2001. Since many people asked for copies we are making it available in the hope that it may be useful. The conjecture was proved by Kawarabayashi and Kreutzer in arXiv:1411.5681.

preprint2015arXiv

Induced subgraphs of graphs with large chromatic number. I. Odd holes

An odd hole in a graph is an induced subgraph which is a cycle of odd length at least five. In 1985, A. Gyarfas made the conjecture that for all t there exists n such that every graph with no K_t subgraph and no odd hole is n-colourable. We prove this conjecture.

preprint2015arXiv

Induced subgraphs of graphs with large chromatic number. II. Three steps towards Gyarfas' conjectures

Gyarfas conjectured in 1985 that for all $k$ , $l$ , every graph with no clique of size more than $k$ and no odd hole of length more than $l$ has chromatic number bounded by a function of $k$ and $l$ . We prove three weaker statements: (1) Every triangle-free graph with sufficiently large chromatic number has an odd hole of length different from five; (2) For all $l$ , every triangle-free graph with sufficiently large chromatic number contains either a 5-hole or an odd hole of length more than $l$ ; (3) For all $k$ , $l$ , every graph with no clique of size more than $k$ and sufficiently large chromatic number contains either a 5-hole or a hole of length more than $l$ .

preprint2015arXiv

Unavoidable induced subgraphs in large graphs with no homogeneous sets

A homogeneous set of an $n$ -vertex graph is a set $X$ of vertices ( $2\le |X|\le n-1$ ) such that every vertex not in $X$ is either complete or anticomplete to $X$ . A graph is called prime if it has no homogeneous set. A chain of length $t$ is a sequence of $t+1$ vertices such that for every vertex in the sequence except the first one, its immediate predecessor is its unique neighbor or its unique non-neighbor among all of its predecessors. We prove that for all $n$ , there exists $N$ such that every prime graph with at least $N$ vertices contains one of the following graphs or their complements as an induced subgraph: (1) the graph obtained from $K_{1,n}$ by subdividing every edge once, (2) the line graph of $K_{2,n}$ , (3) the line graph of the graph in (1), (4) the half-graph of height $n$ , (5) a prime graph induced by a chain of length $n$ , (6) two particular graphs obtained from the half-graph of height $n$ by making one side a clique and adding one vertex.

preprint2014arXiv

Discharging cartwheels

In [J. Combin. Theory Ser. B 70 (1997), 2-44] we gave a simplified proof of the Four-Color Theorem. The proof is computer-assisted in the sense that for two lemmas in the article we did not give proofs, and instead asserted that we have verified those statements using a computer. Here we give additional details for one of those lemmas, and we include the original computer programs and data as "ancillary files" accompanying this submission.

preprint2014arXiv

Disjoint dijoins

A dijoin in a digraph is a set of edges meeting every directed cut. D. R. Woodall conjectured in 1976 that if G is a digraph, and every directed cut of G has at least k edges, then there are k pairwise disjoint dijoins. This remains open, but a capacitated version is known to be false. In particular, A. Schrijver gave a digraph G and a subset S of its edge-set, such that every directed cut contains at least two edges in S, and yet there do not exist two disjoint dijoins included in S. In Schrijver's example, G is planar, and the subdigraph formed by the edges in S consists of three disjoint paths. We conjecture that when k = 2, the disconnectedness of S is crucial: more precisely, that if G is a digraph, and S is a subset of the edges of G that forms a connected subdigraph (as an undirected graph), and every directed cut of G contains at least two edges in S, then we can partition S into two dijoins. We prove this in two special cases: when G is planar, and when the subdigraph formed by the edges in S is a subdivision of a caterpillar.

preprint2014arXiv

Disjoint paths in tournaments

Given $k$ pairs of vertices $(s_i,t_i)$ , $1\le i\le k$ , of a digraph $G$ , how can we test whether there exist $k$ vertex-disjoint directed paths from $s_i$ to $t_i$ for $1\le i\le k$ ? This is NP-complete in general digraphs, even for $k = 2$ , but for $k=2$ there is a polynomial-time algorithm when $G$ is a tournament (or more generally, a semicomplete digraph), due to Bang-Jensen and Thomassen. Here we prove that for all fixed $k$ there is a polynomial-time algorithm to solve the problem when $G$ is semicomplete.

preprint2014arXiv

Excluded minors in cubic graphs

Let G be a cubic graph, with girth at least five, such that for every partition X,Y of its vertex set with |X|,|Y|>6 there are at least six edges between X and Y. We prove that if there is no homeomorphic embedding of the Petersen graph in G, and G is not one particular 20-vertex graph, then either G\v is planar for some vertex v, or G can be drawn with crossings in the plane, but with only two crossings, both on the infinite region. We also prove several other theorems of the same kind.

preprint2014arXiv

Girth six cubic graphs have Petersen minors

We prove that every 3-regular graph with no circuit of length less than six has a subgraph isomorphic to a subdivision of the Petersen graph.

preprint2014arXiv

Reducibility in the Four-Color Theorem

preprint2014arXiv

Wheel-free planar graphs

A \emph{wheel} is a graph formed by a chordless cycle $C$ and a vertex $u$ not in $C$ that has at least three neighbors in $C$ . We prove that every 3-connected planar graph that does not contain a wheel as an induced subgraph is either a line graph or has a clique cutset. We prove that every planar graph that does not contain a wheel as an induced subgraph is 3-colorable.

preprint2013arXiv

Bipartite Minors

We introduce a notion of bipartite minors and prove a bipartite analog of Wagner's theorem: a bipartite graph is planar if and only if it does not contain $K_{3,3}$ as a bipartite minor. Similarly, we provide a forbidden minor characterization for outerplanar graphs and forests. We then establish a recursive characterization of bipartite $(2,2)$ -Laman graphs --- a certain family of graphs that contains all maximal bipartite planar graphs.

preprint2013arXiv

Excluding Pairs of Graphs

For a graph $G$ and a set of graphs $\mathcal{H}$ , we say that $G$ is {\em $\mathcal{H}$ -free} if no induced subgraph of $G$ is isomorphic to a member of $\mathcal{H}$ . Given an integer $P>0$ , a graph $G$ , and a set of graphs $\mathcal{F}$ , we say that $G$ {\em admits an $(\mathcal{F},P)$ -partition} if the vertex set of $G$ can be partitioned into $P$ subsets $X_1,..., X_P$ , so that for every $i \in \{1,..., P\}$ , either $|X_i|=1$ , or the subgraph of $G$ induced by $X_i$ is $\{F\}$ -free for some $F \in \mathcal{F}$ . Our first result is the following. For every pair $(H,J)$ of graphs such that $H$ is the disjoint union of two graphs $H_1$ and $H_2$ , and the complement $J^c$ of $J$ is the disjoint union of two graphs $J_1^c$ and $J_2^c$ , there exists an integer $P>0$ such that every $\{H,J\}$ -free graph has an $(\{H_1,H_2,J_1,J_2\},P)$ -partition. Using a similar idea we also give a short proof of one of the results of \cite{heroes}. Our final result is a construction showing that if $\{H,J\}$ are graphs each with at least one edge, then for every pair of integers $r,k$ there exists a graph $G$ such that every $r$ -vertex induced subgraph of $G$ is $\{H,J\}$ -split, but $G$ does not admits an $(\{H,J\},k)$ -partition.

preprint2013arXiv

Immersion in four-edge-connected graphs

Fix g>1. Every graph of large enough tree-width contains a g x g grid as a minor; but here we prove that every four-edge-connected graph of large enough tree-width contains a g x g grid as an immersion (and hence contains any fixed graph with maximum degree at most four as an immersion). This result has a number of applications.

preprint2013arXiv

Rooted grid minors

Intuitively, a tangle of large order in a graph is a highly-connected part of the graph, and it is known that if a graph has a tangle of large order then it has a large grid minor. Here we show that for any k, if G has a tangle of large order and Z is a set of vertices of cardinality k that cannot be separated from the tangle by any separation of order less than k, then G has a large grid minor containing Z, in which the members of Z all belong to the outside of the grid. This is a lemma for use in a later paper.

preprint2013arXiv

The Minimal Automorphism-Free Tree

A finite tree $T$ with $|V(T)| \geq 2$ is called {\it automorphism-free} if there is no non-trivial automorphism of $T$ . Let $\mathcal{AFT}$ be the poset with the element set of all finite automorphism-free trees (up to graph isomorphism) ordered by $T_1 \preceq T_2$ if $T_1$ can be obtained from $T_2$ by successively deleting one leaf at a time in such a way that each intermediate tree is also automorphism-free. In this paper, we prove that $\mathcal{AFT}$ has a unique minimal element. This result gives an affirmative answer to the question asked by Rupinski.

preprint2012arXiv

Counting paths in digraphs

Say a digraph is k-free if it has no directed cycles of length at most k, for positive integers k. Thomasse conjectured that the number of induced 3-vertex directed paths in a simple 2-free digraph on n vertices is at most (n-1)n(n+1)/15. We present an unpublished result of Bondy proving that there are at most 2n^3/25 such paths, and prove that for the class of circular interval digraphs, an upper bound of n^3/16 holds. We also study the problem of bounding the number of (non-induced) 4-vertex paths in 3-free digraphs. We show an upper bound of 4n^4/75 using Bondy's result for Thomasse's conjecture.

preprint2012arXiv

Edge-colouring eight-regular planar graphs

It was conjectured by the third author in about 1973 that every $d$ -regular planar graph (possibly with parallel edges) can be $d$ -edge-coloured, provided that for every odd set $X$ of vertices, there are at least $d$ edges between $X$ and its complement. For $d = 3$ this is the four-colour theorem, and the conjecture has been proved for all $d\le 7$ , by various authors. Here we prove it for $d = 8$ .

preprint2012arXiv

Edge-colouring seven-regular planar graphs

A conjecture due to the fourth author states that every $d$ -regular planar multigraph can be $d$ -edge-coloured, provided that for every odd set $X$ of vertices, there are at least $d$ edges between $X$ and its complement. For $d = 3$ this is the four-colour theorem, and the conjecture has been proved for all $d\le 8$ , by various authors. In particular, two of us proved it when $d=7$ ; and then three of us proved it when $d=8$ . The methods used for the latter give a proof in the $d=7$ case that is simpler than the original, and we present it here.

preprint2012arXiv

Tournament Minors

We say a digraph $G$ is a {\em minor} of a digraph $H$ if $G$ can be obtained from a subdigraph of $H$ by repeatedly contracting a strongly-connected subdigraph to a vertex. Here, we show the class of all tournaments is a well-quasi-order under minor containment.

preprint2011arXiv

A local strengthening of Reed's ω, Δ, χ conjecture for quasi-line graphs

Reed's $ω$ , $Δ$ , $χ$ conjecture proposes that every graph satisfies $χ\leq \lceil\frac 12(Δ+1+ω)\rceil$ ; it is known to hold for all claw-free graphs. In this paper we consider a local strengthening of this conjecture. We prove the local strengthening for line graphs, then note that previous results immediately tell us that the local strengthening holds for all quasi-line graphs. Our proofs lead to polytime algorithms for constructing colourings that achieve our bounds: $O(n^2)$ for line graphs and $O(n^3m^2)$ for quasi-line graphs. For line graphs, this is faster than the best known algorithm for constructing a colouring that achieves the bound of Reed's original conjecture.

preprint2007arXiv

Cycles in dense digraphs

Let G be a digraph (without parallel edges) such that every directed cycle has length at least four; let $β(G)$ denote the size of the smallest subset X in E(G) such that $G\X$ has no directed cycles, and let $γ(G)$ be the number of unordered pairs {u,v} of vertices such that u,v are nonadjacent in G. It is easy to see that if $γ(G) = 0$ then $β(G) = 0$ ; what can we say about $β(G)$ if $γ(G)$ is bounded? We prove that in general $β(G)$ is at most $γ(G)$ . We conjecture that in fact $β(G)$ is at most $γ(G)/2$ (this would be best possible if true), and prove this conjecture in two special cases: 1. when V(G) is the union of two cliques, 2. when the vertices of G can be arranged in a circle such that if distinct u,v,w are in clockwise order and uw is a (directed) edge, then so are both uv and vw.

preprint1993arXiv

Linkless embeddings of graphs in $3$ -space

We announce results about flat (linkless) embeddings of graphs in 3-space. A piecewise-linear embedding of a graph in 3-space is called {\it flat} if every circuit of the graph bounds a disk disjoint from the rest of the graph. We have shown: (i) An embedding is flat if and only if the fundamental group of the complement in 3-space of the embedding of every subgraph is free. (ii) If two flat embeddings of the same graph are not ambient isotopic, then they differ on a subdivision of $K_5$ or $K_{3,3}$ . (iii) Any flat embedding of a graph can be transformed to any other flat embedding of the same graph by ``3-switches'', an analog of 2-switches from the theory of planar embeddings. In particular, any two flat embeddings of a 4-connected graph are either ambient isotopic, or one is ambient isotopic to a mirror image of the other. (iv) A graph has a flat embedding if and only if it has no minor isomorphic to one of seven specified graphs. These are the graphs that can be obtained from $K_6$ by means of $YΔ$ - and $ΔY$ -exchanges.

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.

Paul Seymour

Research overview

Is this your work?

45 publications

Induced paths in graphs without anticomplete cycles

Polynomial bounds for chromatic number. V. Excluding a tree of radius two and a complete multipartite graph

Bipartite graphs with no K6K_6K6​ minor

Dense minors of graphs with independence number two

Polynomial bounds for chromatic number VII. Disjoint holes

Proof of a conjecture of Plummer and Zha

Strengthening Rodl's theorem

Erdos-Hajnal for graphs with no 5-hole

Pure pairs. VII. Homogeneous submatrices in 0/1-matrices with a forbidden submatrix

A survey of χχχ-boundedness

Detecting a long even hole

Detecting a long odd hole

Even-hole-free graphs still have bisimplicial vertices

Finding a shortest odd hole

Finding an induced path that is not a shortest path

Holes with hats and Erdős-Hajnal

Induced subgraphs of bounded treewidth and the container method

New Examples of Minimal Non-Strongly-Perfect Graphs

Pure pairs. I. Trees and linear anticomplete pairs

Pure pairs. II. Excluding all subdivisions of a graph

Clustered Colouring in Minor-Closed Classes

Induced subgraphs of graphs with large chromatic number. III. Long holes

Excluding A Grid Minor In Planar Digraphs

Induced subgraphs of graphs with large chromatic number. I. Odd holes

Induced subgraphs of graphs with large chromatic number. II. Three steps towards Gyarfas' conjectures

Unavoidable induced subgraphs in large graphs with no homogeneous sets

Discharging cartwheels

Disjoint dijoins

Disjoint paths in tournaments

Excluded minors in cubic graphs

Girth six cubic graphs have Petersen minors

Reducibility in the Four-Color Theorem

Wheel-free planar graphs

Bipartite Minors

Excluding Pairs of Graphs

Immersion in four-edge-connected graphs

Rooted grid minors

The Minimal Automorphism-Free Tree

Counting paths in digraphs

Edge-colouring eight-regular planar graphs

Edge-colouring seven-regular planar graphs

Tournament Minors

A local strengthening of Reed's ω, Δ, χ conjecture for quasi-line graphs

Cycles in dense digraphs

Linkless embeddings of graphs in 333-space

See the researcher in context

Building this map preview

Bipartite graphs with no $K_6$ minor

A survey of $χ$ -boundedness

Linkless embeddings of graphs in $3$ -space