Isomorphic bisections of cubic graphs

DOI10.1016/J.JCTB.2021.08.003MaRDI QIDQ1984530zbMATH OpenOpenAlexFDO

Authors Shagnik Das, Alexey Pokrovskiy, Benny Sudakov

Publication date 16 September 2021

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

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)

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.

Recommendations

• Colourings of cubic graphs inducing isomorphic monochromatic subgraphs
• A note on 3-bisections in subcubic graphs
• 2-bisections in claw-free cubic multigraphs
• On 3-bisections in cubic and subcubic graphs
• Graph partitions: recent progresses and some open problems

Cites work

• scientific article; zbMATH DE number 4170917 (Why is no real title available?)
• scientific article; zbMATH DE number 3717365 (Why is no real title available?)
• scientific article; zbMATH DE number 1229605 (Why is no real title available?)
• scientific article; zbMATH DE number 3243267 (Why is no real title available?)
• A note on 2-bisections of claw-free cubic graphs
• Bounded size components -- partitions and transversals.
• Colourings of cubic graphs inducing isomorphic monochromatic subgraphs
• Defective and clustered graph colouring
• Flows and bisections in cubic graphs
• Internal partitions of regular graphs
• On isomorphic linear partitions in cubic graphs
• On linear k-arboricity
• On the linear k-arboricity of cubic graphs
• 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

Cited in

(5)

• A note on 2-bisections of claw-free cubic graphs
• Irreducible pseudo 2-factor isomorphic cubic bipartite graphs
• Colourings of cubic graphs inducing isomorphic monochromatic subgraphs
• On the bipartition of 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)