Graphs of large girth with prescribed partial circular colourings

被引:1
|
作者
Pan, ZS [1 ]
Zhu, XD
机构
[1] Natl Sun Yat Sen Univ, Dept Appl Math, Kaohsiung 80424, Taiwan
[2] Natl Ctr Theoret Sci, Hsinchu, Taiwan
关键词
circular chromatic number; girth; uniquely colourable;
D O I
10.1007/s00373-004-0596-6
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
This paper completes the constructive proof of the following result: Suppose p/q >= 2 is a rational number, A is a finite set and f(1), f(2,)...,f(n) 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 A subset of V, such that G has exactly n (p, q)-colourings (up to equivalence) g(1), g(2),...,g(n), and each g(i) is an extension of f(i). A probabilistic proof of this result was given in [8]. A constructive proof of the case p/q >= 3 was given in [7].
引用
收藏
页码:119 / 129
页数:11
相关论文
共 50 条
  • [1] Graphs of Large Girth with Prescribed Partial Circular Colourings
    Zhishi Pan
    Xuding Zhu
    Graphs and Combinatorics, 2005, 21 : 119 - 129
  • [2] Circular choosability of planar graphs with large girth
    Wang, Guanghui
    Liu, Guizhen
    ARS COMBINATORIA, 2011, 99 : 65 - 73
  • [3] The circular chromatic number of series-parallel graphs with large girth
    Chien, CY
    Zhu, XD
    JOURNAL OF GRAPH THEORY, 2000, 33 (04) : 185 - 198
  • [4] ON COLOURING ORIENTED GRAPHS OF LARGE GIRTH
    Kayll, P. Mark
    Morris, Michael
    CONTRIBUTIONS TO DISCRETE MATHEMATICS, 2023, 18 (02) : 234 - 243
  • [5] The circular chromatic number of series-parallel graphs of large odd girth
    Pan, ZS
    Zhu, XD
    DISCRETE MATHEMATICS, 2002, 245 (1-3) : 235 - 246
  • [6] On the minimum order of extremal graphs to have a prescribed girth
    Balbuena, C.
    Garcia-Vazquez, P.
    SIAM JOURNAL ON DISCRETE MATHEMATICS, 2007, 21 (01) : 251 - 257
  • [7] LIGHT GRAPHS IN PLANAR GRAPHS OF LARGE GIRTH
    Hudak, Peter
    Macekova, Maria
    Madaras, Tomas
    Siroczki, Pavol
    DISCUSSIONES MATHEMATICAE GRAPH THEORY, 2016, 36 (01) : 227 - 238
  • [8] The circular chromatic index of graphs of high girth
    Kaiser, Tomas
    Kral, Daniel
    Skrekovski, Riste
    Zhu, Xuding
    JOURNAL OF COMBINATORIAL THEORY SERIES B, 2007, 97 (01) : 1 - 13
  • [9] Topological minors in graphs of large girth
    Kühn, D
    Osthus, D
    JOURNAL OF COMBINATORIAL THEORY SERIES B, 2002, 86 (02) : 364 - 380
  • [10] Secret sharing on large girth graphs
    László Csirmaz
    Péter Ligeti
    Cryptography and Communications, 2019, 11 : 399 - 410