3-Flows with Large Support
We prove that every 3-edge-connected graph has a 3-flow with the property that . The graph demonstrates that this ratio is best possible; there is an infinite family where is tight.
Source author record
Jessica McDonald
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
12works
1topics
4close collaborators
Published work
12 publications
preprint2020arXiv
On clique immersions in line graphs
We prove that if L(G) immerses Kt then L(mG) immerses Kmt, where mG is the graph obtained from G by replacing each edge in G with a parallel edge of multiplicity m. This implies that when G is a simple graph, L(mG) satisfies a conjecture of Abu-Khzam and Langston. We also show that when G is a line graph, G has a Kt-immersion iff G has a Kt-minor whenever t≤4, but this equivalence fails in both directions when t≥5.
Open access
preprint2016arXiv
On a limit of the method of Tashkinov trees for edge-colouring
The main technique used to edge-colour graphs requiring Δ+2 or more colours is the method of Tashkinov trees. We present a specific limit to this method, in terms of Kempe changes. We also provide a new Tashkinov tree extension.
Open access
preprint2015arXiv
A list analog of Vizing's Theorem for simple graphs with triangles but no other odd cycles
This paper has been withdrawn by the author. Peterson and Woodall previously proved that the list-edge-colouring conjecture holds for graphs without odd cycles of length 5 or longer. D. Peterson and D. R. Woodall, Edge-choosability in line-perfect multigraphs, Discrete Mathematics 202 (1999), 191-199. D. Peterson and D. R. Woodall, Erratum to "Edge-choosability in line-perfect multigraphs", Discrete Mathematics 260 (2003), 323-326.
Open access
preprint2015arXiv
On Galvin orientations of line graphs and list-edge-colouring
The notion of a Galvin orientation of a line graph is introduced, generalizing the idea used by Galvin in his landmark proof of the list-edge-colouring conjecture for bipartite graphs. If L(G) has a proper Galvin orientation with respect to k, then it immediately implies that G is k-list-edge-colourable, but the converse is not true. The stronger property is studied in graphs of the form `bipartite plus an edge', the Petersen graph, cliques, and simple graphs without odd cycles of length 5 or longer.
Open access
preprint2015arXiv
Packing Steiner Trees
Let T be a distinguished subset of vertices in a graph G. A T-\emph{Steiner tree} is a subgraph of G that is a tree and that spans T. Kriesell conjectured that G contains k pairwise edge-disjoint T-Steiner trees provided that every edge-cut of G that separates T has size ≥2k. When T=V(G) a T-Steiner tree is a spanning tree and the conjecture is a consequence of a classic theorem due to Nash-Williams and Tutte. Lau proved that Kriesell's conjecture holds when 2k is replaced by 24k, and recently West and Wu have lowered this value to 6.5k. Our main result makes a further improvement to 5k+4.
Open access
preprint2015arXiv
Packing triangles in weighted graphs
Tuza conjectured that for every graph G, the maximum size ν of a set of edge-disjoint triangles and minimum size τ of a set of edges meeting all triangles satisfy τ≤2ν. We consider an edge-weighted version of this conjecture, which amounts to packing and covering triangles in multigraphs. Several known results about the original problem are shown to be true in this context, and some are improved. In particular, we answer a question of Krivelevich who proved that τ≤2ν∗ (where ν∗ is the fractional version of ν), and asked if this is tight. We prove that τ≤2ν∗−61ν∗ and show that this bound is essentially best possible.
Open access
preprint2012arXiv
A note on forbidding clique immersions
Robertson and Seymour proved that the relation of graph immersion is well-quasi-ordered for finite graphs. Their proof uses the results of graph minors theory. Surprisingly, there is a very short proof of the corresponding rough structure theorem for graphs without Kt-immersions; it is based on the Gomory-Hu theorem. The same proof also works to establish a rough structure theorem for Eulerian digraphs without Kt-immersions, where Kt denotes the bidirected complete digraph of order t.
Open access
preprint2011arXiv
Immersing complete digraphs
We consider the problem of immersing the complete digraph on t vertices in a simple digraph. For Eulerian digraphs, we show that such an immersion always exists whenever minimum degree is at least t(t-1), and for t at most 4 minimum degree at least t-1 suffices. On the other hand, we show that there exist non-Eulerian digraphs with all vertices of arbitrarily high in- and outdegree which do not contain an immersion of the complete digraph on 3 vertices. As a side result, we obtain a construction of digraphs with large outdegree in which all cycles have odd length, simplifying a former construction of such graphs by Thomassen.
Open access
preprint2011arXiv
Minimum degree condition forcing complete graph immersion
An immersion of a graph H into a graph G is a one-to-one mapping f:V(H)→V(G) and a collection of edge-disjoint paths in G, one for each edge of H, such that the path Puv corresponding to edge uv has endpoints f(u) and f(v). The immersion is strong if the paths Puv are internally disjoint from f(V(H)). It is proved that for every positive integer t, every simple graph of minimum degree at least 200t contains a strong immersion of the complete graph Kt. For dense graphs one can say even more. If the graph has order n and has 2cn2 edges, then there is a strong immersion of the complete graph on at least c2n vertices in G in which each path Puv is of length 2. As an application of these results, we resolve a problem raised by Paul Seymour by proving that the line graph of every simple graph with average degree d has a clique minor of order at least cd3/2, where c>0 is an absolute constant. For small values of t, 1≤t≤7, every simple graph of minimum degree at least t−1 contains an immersion of Kt (Lescure and Meyniel, DeVos et al.). We provide a general class of examples showing that this does not hold when t is large.
Open access
preprint2010arXiv
Average Degree in Graph Powers
The kth power of a simple graph G, denoted G^k, is the graph with vertex set V(G) where two vertices are adjacent if they are within distance k in G. We are interested in finding lower bounds on the average degree of G^k. Here we prove that if G is connected with minimum degree d > 2 and |V(G)| > (8/3)d, then G^4 has average degree at least (7/3)d. We also prove that if G is a connected d-regular graph on n vertices with diameter at least 3k+3, then the average degree of G^{3k+2} is at least (2k+1)(d+1) - k(k+1) (d+1)^2/n - 1. Both of these results are shown to be essentially best possible; the second is best possible even when n/d is arbitrarily large.
Open access
preprint2010arXiv
Kempe equivalence of edge-colourings in subcubic and subquartic graphs
It is proved that all 4-edge-colourings of a (sub)cubic graph are Kempe equivalent. This resolves a conjecture of the second author. In fact, it is found that the maximum degree Delta=3 is a threshold for Kempe equivalence of (Delta+1)-edge-colourings, as such an equivalence does not hold in general when Delta=4. One extra colour allows a similar result in this latter case however, namely, when Delta<=4 it is shown that all (Delta+2)-edge-colourings are Kempe equivalent.
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.