An Analogy Between Edge Colourings and Differentiable Manifolds, with a New Perspective on 3-Critical Graphs
An Analogy Between Edge Colourings and Differentiable Manifolds, with a New Perspective on 3-Critical Graphs
复制标题
边着色和可微流形之间的类比，以及三临界图的新视角
DOI：
10.1007/s00373-014-1512-3
复制
发表时间：
2015
影响因子：
0.7
通讯作者：
A. Vietri
中科院分区：
文献类型：
--
作者：
A. Vietri
图或更一般地多重图可以解释为星族（每个顶点对应一个星），它们在某些边上充分相交，从而生成全局邻接结构。边缘着色可以理解为对每个星形的单射颜色分配，在相邻顶点上享有“兼容性”属性：因为，任何两个相交的星形显然必须在每对重叠边上获得相同的颜色（多重图的星形可能有多个重叠）。上述解释证明了一些关键定义的合理性，这些定义使得边缘着色与流形上的可微分图集非常相似。在简单图的情况下，类别 1 和类别 2 之间的区别成为可定向地图集和不可定向地图集之间的区别。特别是，在大多数情况下，具有 $$2\le k\le 3$$2≤k≤3 的 $$k$$k 临界图被证明是极值边或顶点识别的结果，这类似于从矩形带产生莫比乌斯带的拓扑识别。沿着条带移动相当于在图形的局部图表（星形）上传输固定颜色。因此，我们重新审视小型三临界图的已知分类，特别强调在识别极值后失去可定向性（即变得临界）的各种类型的图。
A graph or more generally a multigraph can be interpreted as a family of stars—one star for each vertex—which adequately intersect on certain edges, so as to generate a global adjacency structure. An edge colouring can be read as an injective assignment of colours to each star, enjoying a “compatibility” property on adjacent vertices: for, any two intersecting stars must obviously get the same colour on each pair of overlapping edges (stars of multigraphs may have more than one overlap). The above interpretation justifies some key definitions which make an edge colouring rather similar to a differentiable atlas on a manifold. In the case of simple graphs, the distinction between class 1 and class 2 becomes the distinction between orientable and non-orientable atlases. In particular, $$k$$k-critical graphs with $$2\le k\le 3$$2≤k≤3 are shown to be, in most cases, the result of an identification of extremal edges or vertices which is analogous to the topological identification yielding the Möbius strip from the rectangular strip. Moving along the strip is equivalent to transmitting a fixed colour across the local charts (stars) of the graph. Accordingly, we revisit the known classification of small 3-critical graphs, with a specific stress on the various types of graphs which lose orientability (i.e. become critical) after the identification of their extremes.