Graphs of Large Girth with Prescribed Partial Circular Colourings |
| |
Authors: | Zhishi Pan Xuding Zhu |
| |
Affiliation: | (1) Department of Applied Mathematics, National Sun Yat-sen University, Kaohsiung, Taiwan, 80424;(2) National Center for Theoretical Sciences, Taiwan |
| |
Abstract: | This paper completes the constructive proof of the following result: Suppose p/q 2 is a rational number, A is a finite set and f1,f2,···,fn are mappings from A to {0,1,···,p–1}. Then for any integer g, there is a graph G=(V,E) of girth at least g with such that G has exactly n (p,q)-colourings (up to equivalence) g1,g2,···,gn, and each gi is an extension of fi. A probabilistic proof of this result was given in [8]. A constructive proof of the case p/q 3 was given in [7].This research was partially supported by the National Science Council under grant NSC91-2115-M-110-004 |
| |
Keywords: | Circular chromatic number Girth Uniquely colourable |
本文献已被 SpringerLink 等数据库收录! |
|