Graph Coloring and the Immersion Order
Graph Coloring and the Immersion Order
复制标题
图形着色和浸入顺序
DOI：
--
复制
发表时间：
2003
期刊：
影响因子：
--
通讯作者：
M. Langston
中科院分区：
文献类型：
--
作者：
F. Abu;M. Langston
考虑图形和浸入顺序之间的关系。探索了顶点连接，边缘连接和相关问题。这些导致了这样的猜想，即如果G需要至少T颜色，则G必须将其浸入kt中，这是T顶点上的完整图。提供了支持这种主张的证据。对于t的每个固定值，只能有有限数量的最小反例。这些反示例的特征是基于Kempe链，连通性，切割组和程度边界的特征。事实证明，如果存在的话，最小的反例必须是4-vertex连接和T边缘连接的。
The relationship between graph coloring and the immersion order is considered. Vertex connectivity, edge connectivity and related issues are explored. These lead to the conjecture that, if G requires at least t colors, then G must have immersed within it Kt, the complete graph on t vertices. Evidence in support of such a proposition is presented. For each fixed value of t, there can be only a finite number of minimal counterexamples. These counterexamples are characterized based on Kempe chains, connectivity, cutsets and degree bounds. It is proved that minimal counterexamples must, if any exist, be both 4-vertex-connected and t-edge-connected.