2
$\begingroup$

Let $\mathcal{G}(n)$ be the isomorphism class of simple graphs of order $n$. We say two graphs in $\mathcal{G}(n)$ are chromatic equivalent if their chromatic polynomials have an equal linear coefficient. The resulting equivalence classes $\chi(n)$ under this relation are called the chromatic class of order $n$.

I have the following questions :

  1. What is the cardinality of $\chi(n)$?

  2. What are some references to study about $\chi(n)$?

For small numbers, the cardinality of $\chi(n)$ is equal to 1,1,2,5,12,37,121, . . . But except for a first few terms, it is not matching with any sequence in OEIS.

Thank you.

Improve this question
$\endgroup$
12
  • 1
    $\begingroup$ Why the linear coefficient? $\endgroup$
    – Gerry Myerson
    Commented Aug 30, 2019 at 2:41
  • 1
    $\begingroup$ Linear coefficient counts many interesting objects related to the graph, for example, see the introduction of arxiv.org/abs/1708.06382. I am interested in the combinatorics of the linear coefficient. $\endgroup$
    – GA316
    Commented Aug 30, 2019 at 4:04
  • 1
    $\begingroup$ Have you calculated the cardinality for a few values of $n$? $\endgroup$
    – Gerry Myerson
    Commented Aug 30, 2019 at 7:39
  • 2
    $\begingroup$ Yes, I have. Please check the question. I have just added these details. $\endgroup$
    – GA316
    Commented Aug 30, 2019 at 9:28
  • 1
    $\begingroup$ @MartinRubey for any disconnected the value will be zero. So we can get the data from connected graphs by subtracting one. $\endgroup$
    – John Machacek
    Commented Aug 30, 2019 at 14:22

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .