Switching techniques for edge decompositions of graphs

Research output: Chapter in Book/Report/Conference proceedingChapter (Book)Researchpeer-review

Abstract

This article concerns a class of techniques, herein referred to as edge switching techniques, that enable a new edge decomposition to be obtained from an existing one by interchanging edges between the subgraphs in the decomposition. These techniques can be viewed as generalisations of classical path switching methods for proper edge colourings. Their use in other edge decomposition settings dates back at least to 1980, but the last ten years have seen them rapidly developed and employed to resolve Lindner's conjecture on embedding partial Steiner triple systems, Alspach's cycle decomposition problem, and numerous other questions. Here we aim to give the reader a gentle introduction to these techniques and to some of their most significant applications beyond edge colouring.
Original languageEnglish
Title of host publicationSurveys in Combinatorics 2017
EditorsAnders Claesson, Mark Dukes, Sergey Kitaev, David Manlove, Kitty Meeks
Place of PublicationCambridge UK
PublisherCambridge University Press
Chapter5
Pages238-271
Number of pages34
ISBN (Electronic)9781108332699
DOIs
Publication statusPublished - 30 Jun 2017

Publication series

NameLondon Mathematical Society Lecture Note Series
PublisherCambridge University Press
Volume440

Cite this

Horsley, D. (2017). Switching techniques for edge decompositions of graphs. In A. Claesson, M. Dukes, S. Kitaev, D. Manlove, & K. Meeks (Eds.), Surveys in Combinatorics 2017 (pp. 238-271). (London Mathematical Society Lecture Note Series; Vol. 440). Cambridge University Press. https://doi.org/10.1017/9781108332699