Isomorphic bisections of cubic graphs

DOI10.1016/J.JCTB.2021.08.003zbMATH Open1473.05238arXiv2012.05222OpenAlexW3198217503MaRDI QIDQ1984530FDOQ1984530

Shagnik Das, Benny Sudakov, Alexey Pokrovskiy

Publication date: 16 September 2021

Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/2012.05222

zbMATH Keywords

cubic graphsclustered colouring

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Connectivity (05C40) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Partitioning into graphs with only small components
• Two-coloring the edges of a cubic graph such that each monochromatic component is a path of length at most 5
• On the linear \(k\)-arboricity of cubic graphs
• On linear k-arboricity
• On isomorphic linear partitions in cubic graphs
• Bounded size components -- partitions and transversals.
• Graph coloring with no large monochromatic components
• Colourings of cubic graphs inducing isomorphic monochromatic subgraphs
• Flows and Bisections in Cubic Graphs
• Defective and clustered graph colouring
• Internal partitions of regular graphs
• A note on 2-bisections of claw-free cubic graphs

Cited In (2)

• Irreducible pseudo 2-factor isomorphic cubic bipartite graphs
• ON ISOMORPHISMS OF VERTEX-TRANSITIVE CUBIC GRAPHS

This page was built for publication: Isomorphic bisections of cubic graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1984530)