A short proof of a conjecture on the Tr-choice number of even cycles

R.A. Sitters

    Research output: Book/ReportReportProfessional

    113 Downloads (Pure)

    Abstract

    In this note we prove that the $T_r$-choice number of the cycle $C_{2n}$ is equal to the $T_r$-choice number of the path (tree) on $4n-1$ vertices, i.e. $T_r$-$ch(C_{2n}) = \left\lfloor(2r+2)(4n-2)/(4n-1)\right\rfloor + 1$. This solves a recent conjecture of Alon and Zaks.
    Original languageUndefined
    Place of PublicationEnschede
    PublisherUniversity of Twente
    Number of pages5
    ISBN (Print)0169-2690
    Publication statusPublished - 1998

    Publication series

    NameMemorandum / Faculty of Mathematical Sciences
    PublisherDepartment of Applied Mathematics, University of Twente
    No.1477
    ISSN (Print)0169-2690

    Keywords

    • MSC-05C15
    • Graph colouring
    • Tr-choice number
    • even cycle
    • METIS-141277
    • choosability
    • EWI-3297
    • list colouring
    • IR-65666
    • choice number

    Cite this