ON UNIQUELY -G k-COLOURABLE GRAPHS
作者:
J.I. Brown,
D.G. Corneil,
期刊:
Quaestiones Mathematicae
(Taylor Available online 1992)
卷期:
Volume 15,
issue 4
页码: 477-487
ISSN:1607-3606
年代: 1992
DOI:10.1080/16073606.1992.9631706
出版商: Taylor & Francis Group
关键词: 05C15
数据来源: Taylor
摘要:
Given graphsFandGand a nonnegative integerk, a map Π:V(F) → + {lm…,k} is a -Gk-colouring ofFif the subgraphs induced by each colour class do not containGas an induced subgraph;Fis -Gk-chromaticifFhas a -Gk-colouring but no -G(k—1)-colouring. Further, we sayFisuniquely-Gk-colourableif and only ifFis -Gk-chromatic and, up to a permutation of colours, it has only one -Gk-colouring. Such notions are extensions of the well known corresponding definitions from chromatic theory. In a previous paper (J. Graph. Th. 11 (1987), 87–99), the authors conjectured that for all graphs G of order at least two and all nonnegative integers k there exist uniquely -Gk-colourable graphs. We show here that the conjecture holds wheneverGor its complement is 2-connected.
点击下载:
PDF (425KB)
返 回