Das, S;
Pokrovskiy, A;
Sudakov, B;
(2021)
Isomorphic bisections of cubic graphs.
Journal of Combinatorial Theory, Series B
, 151
pp. 465-481.
10.1016/j.jctb.2021.08.003.
Preview |
Text
Cubic_bisections (3).pdf - Accepted Version Download (451kB) | Preview |
Abstract
Graph partitioning, or the dividing of a graph into two or more parts based on certain conditions, arises naturally throughout discrete mathematics, and problems of this kind have been studied extensively. In the 1990s, Ando conjectured that the vertices of every cubic graph can be partitioned into two parts that induce isomorphic subgraphs. Using probabilistic methods together with delicate recolouring arguments, we prove Ando's conjecture for large connected graphs.
| Type: | Article |
|---|---|
| Title: | Isomorphic bisections of cubic graphs |
| Open access status: | An open access version is available from UCL Discovery |
| DOI: | 10.1016/j.jctb.2021.08.003 |
| Publisher version: | https://doi.org/10.1016/j.jctb.2021.08.003 |
| Language: | English |
| Additional information: | This version is the author accepted manuscript. For information on re-use, please refer to the publisher’s terms and conditions. |
| Keywords: | Science & Technology, Physical Sciences, Mathematics, Cubic graphs, Clustered colouring, PARTITIONS |
| UCL classification: | UCL UCL > Provost and Vice Provost Offices > UCL BEAMS UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Maths and Physical Sciences UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Maths and Physical Sciences > Dept of Mathematics |
| URI: | https://discovery-pp.ucl.ac.uk/id/eprint/10142093 |
Archive Staff Only
 |
View Item |
