首页   按字顺浏览 期刊浏览 卷期浏览 ON UNIQUELY -G k-COLOURABLE GRAPHS
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)



返 回