1
$\begingroup$

Is there a way to obtain the chromatic polynomial of the line graph of a regular simple graph, having known the chromatic polynomial of the graph?

There already exist characterizations of line graph of a simple graph, like it consists of several cliques of order equal to the maximum degree of the graph, any two being joined at at most one unique vertex. In addition, the skeleton graph of the cliques, that is the graph formed by taking each clique as a vertex, is nothing but the graph itself. Can we use these characterizations along with knowing the chromatic polynomial of the graph beforehand, to determine the required polynomial? What can be said about the complexity of this problem? Can there be a polynomial time algorithm to compute it, starting from the chromatic polynomial of the graph? Thanks beforehand.

Improve this question
$\endgroup$
3
  • $\begingroup$ If anything were known I might expect it to be discussed under the term "edge chromatic polynomial". $\endgroup$
    – Ben Barber
    Commented Jul 8, 2020 at 19:15
  • $\begingroup$ @BenBarber yes, a similar question exists here, but I also ask about complexity and a method starting from the chromatic polynomial of the graph $\endgroup$
    – vidyarthi
    Commented Jul 8, 2020 at 19:23
  • $\begingroup$ An observation: there are graphs with the same chromatic polynomial but different edge chromatic polynomials (various trees, say), so any such algorithm cannot depend solely on the chromatic polynomial. $\endgroup$
    – Ben Barber
    Commented Jul 8, 2020 at 20:28

0

Reset to default

You must log in to answer this question.