ISSN 0253-2778

CN 34-1054/N

open
Free to Publish. Free to Read.
Open AccessOpen Access JUSTC Research Articles: Mathematics

Cycle lengths in graphs of chromatic number five and six

  • School of Mathematical Sciences, University of Science and Technology of China, Hefei 230026, China

Cite this:
https://doi.org/10.52396/JUST-2021-0119
  • Received Date: 17 April 2021
  • Rev Recd Date: 25 May 2021
  • Publish Date: 31 May 2021
    Abstract

  • Abstract

    A problem was proposed by Moore and West to determine whether every (k+1)-critical non-complete graph has a cycle of length 2 modulo k. We prove a stronger result that for k=4, 5, every (k+1)-critical non-complete graph contains cycles of all lengths modulo k.

    Abstract

    A problem was proposed by Moore and West to determine whether every (k+1)-critical non-complete graph has a cycle of length 2 modulo k. We prove a stronger result that for k=4, 5, every (k+1)-critical non-complete graph contains cycles of all lengths modulo k.
    • FullText(HTML)
  • loading
    • References(10)
  • [1]
    Bollobás B. Cycles modulo k. Bull. London Math. Soc., 1977, 9: 97-98.
    [2]
    Diwan A. Cycles of even lengths modulo k. J. Graph Theory, 2010, 65: 246-252.
    [3]
    Erdös P. Some of my favourite problems in various branches of combinatorics. Annals of Discrete Mathematics, 1992, 51: 69-79.
    [4]
    Fan G. Distribution of cycle lengths in graphs. J. Combin. Theory Ser. B., 2002, 84: 187-202.
    [5]
    Liu C, Ma J. Cycle lengths and minimum degree of graphs. J. Combin. Theory Ser. B., 2018, 128: 66-95.
    [6]
    Sudakov B, Verstraëte J. The extremal function for cycles of length l mod k. The Electronic Journal of Combinatorics, 2017, 24(1): #P1.7.
    [7]
    Thomassen C. Graph decomposition with applications to subdivisions and path systems modulo k. J. Graph Theory, 1983, 7: 261-271.
    [8]
    Verstraëte J. On arithmetic progressions of cycle lengths in graphs. Combin. Probab. Comput., 2000, 9: 369-373.
    [9]
    Moore B, West D B. Cycles in color-critical graphs. https://export.arxiv.org/abs/1912.03754v2.
    [10]
    Gao J, Huo Q, Ma J. A strengthening on odd cycles in graphs of given chromatic number.SIAM J. Discrete Math., 2021, 35(4): 2317-2327.
    • Supplements(0)
    • Related Articles
    • Track Citations
  • 加载中

Catalog

    |
    Get Citation
    PDF
    XML
    [1]
    Bollobás B. Cycles modulo k. Bull. London Math. Soc., 1977, 9: 97-98.
    [2]
    Diwan A. Cycles of even lengths modulo k. J. Graph Theory, 2010, 65: 246-252.
    [3]
    Erdös P. Some of my favourite problems in various branches of combinatorics. Annals of Discrete Mathematics, 1992, 51: 69-79.
    [4]
    Fan G. Distribution of cycle lengths in graphs. J. Combin. Theory Ser. B., 2002, 84: 187-202.
    [5]
    Liu C, Ma J. Cycle lengths and minimum degree of graphs. J. Combin. Theory Ser. B., 2018, 128: 66-95.
    [6]
    Sudakov B, Verstraëte J. The extremal function for cycles of length l mod k. The Electronic Journal of Combinatorics, 2017, 24(1): #P1.7.
    [7]
    Thomassen C. Graph decomposition with applications to subdivisions and path systems modulo k. J. Graph Theory, 1983, 7: 261-271.
    [8]
    Verstraëte J. On arithmetic progressions of cycle lengths in graphs. Combin. Probab. Comput., 2000, 9: 369-373.
    [9]
    Moore B, West D B. Cycles in color-critical graphs. https://export.arxiv.org/abs/1912.03754v2.
    [10]
    Gao J, Huo Q, Ma J. A strengthening on odd cycles in graphs of given chromatic number.SIAM J. Discrete Math., 2021, 35(4): 2317-2327.
    Recommended articles
    TrendMD
    Volume 51 Issue 5 page: 374-381
    Cover

    Article Metrics

    Article views (186) PDF downloads(392)
    Proportional views

    Copyright © Editorial Office of JUSTC, All Rights Reserved. 皖ICP备05002528号

    Supported by: Beijing Renhe Information Technology Co. Ltd    

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return