Bounds for the smallest $k$-chromatic graphs of given girth
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 ob...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Discrete Mathematics & Theoretical Computer Science
2019-03-01
|
| Series: | Discrete Mathematics & Theoretical Computer Science |
| Subjects: | |
| Online Access: | https://dmtcs.episciences.org/4576/pdf |
| _version_ | 1797270045760421888 |
|---|---|
| author | Geoffrey Exoo Jan Goedgebeur |
| author_facet | Geoffrey Exoo Jan Goedgebeur |
| author_sort | Geoffrey Exoo |
| collection | DOAJ |
| description | 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$. |
| first_indexed | 2024-04-25T01:58:02Z |
| format | Article |
| id | doaj.art-f5ecf4b8a06c44019c3ad52b67526b59 |
| institution | Directory Open Access Journal |
| issn | 1365-8050 |
| language | English |
| last_indexed | 2024-04-25T01:58:02Z |
| publishDate | 2019-03-01 |
| publisher | Discrete Mathematics & Theoretical Computer Science |
| record_format | Article |
| series | Discrete Mathematics & Theoretical Computer Science |
| spelling | doaj.art-f5ecf4b8a06c44019c3ad52b67526b592024-03-07T15:39:17ZengDiscrete Mathematics & Theoretical Computer ScienceDiscrete Mathematics & Theoretical Computer Science1365-80502019-03-01Vol. 21 no. 3Graph Theory10.23638/DMTCS-21-3-94576Bounds for the smallest $k$-chromatic graphs of given girthGeoffrey ExooJan Goedgebeurhttps://orcid.org/0000-0001-8984-2463Let $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$.https://dmtcs.episciences.org/4576/pdfmathematics - combinatoricscomputer science - discrete mathematics05c30, 05c85, 68r10 |
| spellingShingle | Geoffrey Exoo Jan Goedgebeur Bounds for the smallest $k$-chromatic graphs of given girth Discrete Mathematics & Theoretical Computer Science mathematics - combinatorics computer science - discrete mathematics 05c30, 05c85, 68r10 |
| title | Bounds for the smallest $k$-chromatic graphs of given girth |
| title_full | Bounds for the smallest $k$-chromatic graphs of given girth |
| title_fullStr | Bounds for the smallest $k$-chromatic graphs of given girth |
| title_full_unstemmed | Bounds for the smallest $k$-chromatic graphs of given girth |
| title_short | Bounds for the smallest $k$-chromatic graphs of given girth |
| title_sort | bounds for the smallest k chromatic graphs of given girth |
| topic | mathematics - combinatorics computer science - discrete mathematics 05c30, 05c85, 68r10 |
| url | https://dmtcs.episciences.org/4576/pdf |
| work_keys_str_mv | AT geoffreyexoo boundsforthesmallestkchromaticgraphsofgivengirth AT jangoedgebeur boundsforthesmallestkchromaticgraphsofgivengirth |