Reconfiguration graphs for vertex colourings of chordal and chordal bipartite graphs
Reconfiguration graphs for vertex colourings of chordal and chordal bipartite graphs
复制标题
DOI：
10.1007/s10878-012-9490-y
复制
发表时间：
2012-04
影响因子：
1
通讯作者：
Marthe Bonamy;Matthew Johnson;I. Lignos;V. Patel;D. Paulusma
中科院分区：
文献类型：
--
作者：
Marthe Bonamy;Matthew Johnson;I. Lignos;V. Patel;D. Paulusma
图G =（V，E）的AK-着色是c：V→{1，2，.，k}使得c（u）≠c（v）的映射. G的k-着色的重构图包含G的k-着色作为其顶点集，并且如果两个着色在G的一个顶点上的颜色不同，则两个着色由边连接。本文引入了一类k-色密度图，我们称之为k-色密度图。我们证明了对于每一个k-色稠密图G，G的k-着色的重构图是连通的，并且其直径为O（|V| 2），对所有的k ≥k+1。我们证明了这个图类包含k-列弦图，并且当k =2时，它包含所有的弦二部图。此外，我们还证明了对每个k ≥2，存在k-列弦图G，其（k+1）-着色的重构图的直径为Θ（|V| 2）。
Ak-colouring of a graphG=(V,E) is a mappingc:V→{1,2,…,k} such thatc(u)≠c(v) wheneveruvis an edge. The reconfiguration graph of thek-colourings ofGcontains as its vertex set thek-colourings ofG, and two colourings are joined by an edge if they differ in colour on just one vertex ofG. We introduce a class ofk-colourable graphs, which we callk-colour-densegraphs. We show that for eachk-colour-dense graphG, the reconfiguration graph of theℓ-colourings ofGis connected and has diameterO(|V|2), for allℓ≥k+1. We show that this graph class contains thek-colourable chordal graphs and that it contains all chordal bipartite graphs whenk=2. Moreover, we prove that for eachk≥2 there is ak-colourable chordal graphGwhose reconfiguration graph of the (k+1)-colourings has diameter Θ(|V|2).