4 citations · 8 across the 8 of their papers we have counts for
10 papers
Graphs of Linear Growth have Bounded Treewidth
Rutger Campbell, Marc Distel, J. Pascal Gollin +5
A graph class has linear growth if, for each graph and every positive integer , every subgraph of with radius at most contains v…
Intersecting longest paths in chordal graphs
Daniel J. Harvey, Michael S. Payne
We consider the size of the smallest set of vertices required to intersect every longest path in a chordal graph. Such sets are known as longest path transversals. We show that if…
Chromatic roots at 2 and at the Beraha number
Daniel J. Harvey, Gordon F. Royle
By the construction of suitable graphs and the determination of their chromatic polynomials, we resolve two open questions concerning real chromatic roots. First we exhibit graphs…
Average degree conditions forcing a minor
Daniel J. Harvey, David R. Wood
Mader first proved that high average degree forces a given graph as a minor. Often motivated by Hadwiger's Conjecture, much research has focused on the average degree required to f…
Cycles of given size in a dense graph
Daniel J. Harvey, David R. Wood
We generalise a result of Corrádi and Hajnal and show that every graph with average degree at least contains vertex disjoint cycles, each of order at least …
The Treewidth of Line Graphs
Daniel J. Harvey, David R. Wood
The treewidth of a graph is an important invariant in structural and algorithmic graph theory. This paper studies the treewidth of line graphs. We show that determining the treewid…
Parameters Tied to Treewidth
Daniel J. Harvey, David R. Wood
Treewidth is a graph parameter of fundamental importance to algorithmic and structural graph theory. This paper surveys several graph parameters tied to treewidth, including separa…
Treewidth of the Kneser Graph and the Erdős-Ko-Rado Theorem
Daniel J. Harvey, David R. Wood
Treewidth is an important and well-known graph parameter that measures the complexity of a graph. The Kneser graph Kneser(n,k) is the graph with vertex set , such t…
Treewidth of the Line Graph of Complete and Complete Multipartite Graphs
Daniel J. Harvey, David R. Wood
In recent papers by Grohe and Marx, the treewidth of the line graph of the complete graph is a critical example. We determine the exact treewidth of the line graph of the complete…
A linear-time algorithm for finding a complete graph minor in a dense graph
Vida Dujmović, Daniel J. Harvey, Gwenaël Joret +2
Let g(t) be the minimum number such that every graph G with average degree d(G) \geq g(t) contains a K_{t}-minor. Such a function is known to exist, as originally shown by Mader. K…