Colourings of cubic graphs inducing isomorphic monochromatic subgraphs
Colourings of cubic graphs inducing isomorphic monochromatic subgraphs
复制标题
立方图的着色诱导同构单色子图
DOI：
10.1002/jgt.22462
复制
发表时间：
2017
影响因子：
0.9
通讯作者：
G. Mazzuoccolo
中科院分区：
文献类型：
--
作者：
M. Abreu;Jan Goedgebeur;D. Labbate;G. Mazzuoccolo
无桥三次图G的k-二分图是其顶点集的2-着色，使得色类具有相同的基数，并且由色类诱导的两个子图中的所有连通分量（以下为单色分量）的阶数至多为k。Ban和Linial猜想，除了Petersen图之外，每个无桥三次图都允许2-二等分。三次图的边集的一个类似问题已经被研究过：Wormald证明了每个三次图G有一个2-边着色，使得两个单色子图是同构的线性森林（即，一个森林的组成部分是路）。最后，Ando证明了每一个三次图都有一个二分法，使得两个导出单色子图同构。在本文中，我们提供了证据证明Ban‐Linial和Wormald的猜想与Ando猜想的强关系。此外，我们也给出了计算和理论证据的支持。因此，我们提出了一些比上述假设更强的开放性问题。此外，我们还证明了三次圈置换图的Ban-Linial猜想。作为研究以线性森林为单色分量的三次图的2边着色的副产品，我们还对杰克逊和Wormald提出的关于三次图到线性森林的某些分解的问题给出了否定的回答.
A k ‐bisection of a bridgeless cubic graph G is a 2 ‐colouring of its vertex set such that the colour classes have the same cardinality and all connected components in the two subgraphs induced by the colour classes ( monochromatic components in what follows) have order at most k . Ban and Linial Conjectured that every bridgeless cubic graph admits a 2 ‐bisection except for the Petersen graph. A similar problem for the edge set of cubic graphs has been studied: Wormald conjectured that every cubic graph G with ∣ E ( G ) ∣ ≡ 0 ( mod 2 ) has a 2 ‐edge colouring such that the two monochromatic subgraphs are isomorphic linear forests (ie, a forest whose components are paths). Finally, Ando conjectured that every cubic graph admits a bisection such that the two induced monochromatic subgraphs are isomorphic. In this paper, we provide evidence of a strong relation of the conjectures of Ban‐Linial and Wormald with Ando's Conjecture. Furthermore, we also give computational and theoretical evidence in their support. As a result, we pose some open problems stronger than the above‐mentioned conjectures. Moreover, we prove Ban‐Linial's Conjecture for cubic‐cycle permutation graphs. As a by‐product of studying 2 ‐edge colourings of cubic graphs having linear forests as monochromatic components, we also give a negative answer to a problem posed by Jackson and Wormald about certain decompositions of cubic graphs into linear forests.