Geoffrey Exoo ; Jan Goedgebeur - Bounds for the smallest $k$-chromatic graphs of given girth

dmtcs:4576 - Discrete Mathematics & Theoretical Computer Science, March 11, 2019, Vol. 21 no. 3 -
Bounds for the smallest $k$-chromatic graphs of given girth

Authors: Geoffrey Exoo ; Jan Goedgebeur ORCID-iD

    Let $n_g(k)$ denote the smallest order of a $k$-chromatic graph of girth at least $g$. We consider the problem of determining $n_g(k)$ for small values of $k$ and $g$. After giving an overview of what is known about $n_g(k)$, we provide some new lower bounds based on exhaustive searches, and then obtain several new upper bounds using computer algorithms for the construction of witnesses, and for the verification of their correctness. We also present the first examples of reasonably small order for $k = 4$ and $g > 5$. In particular, the new bounds include: $n_4(7) \leq 77$, $26 \leq n_6(4) \leq 66$, $30 \leq n_7(4) \leq 171$.

    Volume: Vol. 21 no. 3
    Section: Graph Theory
    Published on: March 11, 2019
    Accepted on: February 15, 2019
    Submitted on: June 11, 2018
    Keywords: Mathematics - Combinatorics,Computer Science - Discrete Mathematics,05C30, 05C85, 68R10
      Source : OpenAIRE Graph
    • AF: EAGER: Homomorphism Problems in Digraphs (Dichotomies); Funder: National Science Foundation; Code: 1751765

    Linked publications - datasets - softwares

    Source : ScholeXplorer HasVersion DOI 10.48550/arxiv.1805.06713
    • 10.48550/arxiv.1805.06713
    Bounds for the smallest $k$-chromatic graphs of given girth
    Exoo, Geoffrey ; Goedgebeur, Jan ;

    Consultation statistics

    This page has been seen 701 times.
    This article's PDF has been downloaded 424 times.