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 条
  • [41] The Steiner diameter of a graph with prescribed girth
    Ali, Patrick
    DISCRETE MATHEMATICS, 2013, 313 (12) : 1322 - 1326
  • [42] The average eccentricity of a graph with prescribed girth
    Osaye, F. J.
    DISCRETE MATHEMATICS, 2022, 345 (12)
  • [43] Triangles and Girth in Disk Graphs and Transmission Graphs
    Kaplan, Haim
    Klost, Katharina
    Mulzer, Wolfgang
    Roditty, Liam
    Seiferth, Paul
    Sharir, Micha
    27TH ANNUAL EUROPEAN SYMPOSIUM ON ALGORITHMS (ESA 2019), 2019, 144
  • [44] On the Randic index and girth of graphs
    Liang, Meili
    Liu, Bolian
    DISCRETE APPLIED MATHEMATICS, 2013, 161 (1-2) : 212 - 216
  • [45] Girth and Total Domination in Graphs
    Michael A. Henning
    Anders Yeo
    Graphs and Combinatorics, 2012, 28 : 199 - 214
  • [46] Girth-regular graphs
    Potocnik, Primoz
    Vidali, Janos
    ARS MATHEMATICA CONTEMPORANEA, 2019, 17 (02) : 349 - 368
  • [47] On The Harmonic Index and The Girth for Graphs
    Zhong, Lingping
    ROMANIAN JOURNAL OF INFORMATION SCIENCE AND TECHNOLOGY, 2013, 16 (04): : 253 - 260
  • [48] THE METRIC DIMENSION AND GIRTH OF GRAPHS
    Jannesari, M.
    BULLETIN OF THE IRANIAN MATHEMATICAL SOCIETY, 2015, 41 (03) : 633 - 638
  • [49] Superconnectivity of graphs with odd girth g and even girth h
    Balbuena, C.
    Garcia-Vazquez, P.
    Montejano, L. P.
    DISCRETE APPLIED MATHEMATICS, 2011, 159 (2-3) : 91 - 99
  • [50] Extremal Graphs with Girth Nine
    Zhang Rui
    Sun Yongqi
    Wu Yali
    ARS COMBINATORIA, 2019, 142 : 345 - 356