Finding a Graph given a chromatic polynomial
$begingroup$
Let $f(k) = k^6 - 6k^5 + 15k^4 - 17k^3 + 7k^2$. Show carefully that there is only one simple graph with chromatic polynomial equal to $f(k)$, and find that graph. Verify that the graph you found does indeed have chromatic polynomial equal to $f(k)$.
I have no idea how to go about finding a specific graph given a chromatic polynomial. Despite extensive searching I haven't been able to find any help on this topic.
graph-theory coloring
edited Dec 4 '18 at 22:28
Larry B.
2,801828
asked Dec 4 '18 at 22:25
user2782067user2782067
606
$endgroup$
add a comment |
$begingroup$
Let $f(k) = k^6 - 6k^5 + 15k^4 - 17k^3 + 7k^2$. Show carefully that there is only one simple graph with chromatic polynomial equal to $f(k)$, and find that graph. Verify that the graph you found does indeed have chromatic polynomial equal to $f(k)$.
I have no idea how to go about finding a specific graph given a chromatic polynomial. Despite extensive searching I haven't been able to find any help on this topic.
graph-theory coloring
edited Dec 4 '18 at 22:28
Larry B.
2,801828
asked Dec 4 '18 at 22:25
user2782067user2782067
606
$endgroup$
add a comment |
$begingroup$
Let $f(k) = k^6 - 6k^5 + 15k^4 - 17k^3 + 7k^2$. Show carefully that there is only one simple graph with chromatic polynomial equal to $f(k)$, and find that graph. Verify that the graph you found does indeed have chromatic polynomial equal to $f(k)$.
I have no idea how to go about finding a specific graph given a chromatic polynomial. Despite extensive searching I haven't been able to find any help on this topic.
graph-theory coloring
edited Dec 4 '18 at 22:28
Larry B.
2,801828
asked Dec 4 '18 at 22:25
user2782067user2782067
606
$endgroup$
Let $f(k) = k^6 - 6k^5 + 15k^4 - 17k^3 + 7k^2$. Show carefully that there is only one simple graph with chromatic polynomial equal to $f(k)$, and find that graph. Verify that the graph you found does indeed have chromatic polynomial equal to $f(k)$.
I have no idea how to go about finding a specific graph given a chromatic polynomial. Despite extensive searching I haven't been able to find any help on this topic.
graph-theory coloring
graph-theory coloring
edited Dec 4 '18 at 22:28
Larry B.
2,801828
asked Dec 4 '18 at 22:25
user2782067user2782067
606
edited Dec 4 '18 at 22:28
Larry B.
2,801828
asked Dec 4 '18 at 22:25
user2782067user2782067
606
edited Dec 4 '18 at 22:28
Larry B.
2,801828
edited Dec 4 '18 at 22:28
Larry B.
2,801828
edited Dec 4 '18 at 22:28
Larry B.
2,801828
2,801828
asked Dec 4 '18 at 22:25
user2782067user2782067
606
asked Dec 4 '18 at 22:25
user2782067user2782067
606
asked Dec 4 '18 at 22:25
user2782067user2782067
606
606
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
Let's look at the things we can figure out easily:
- The graph has $6$ vertices, because the polynomial has degree $6$. (In general, the chromatic polynomial of an $n$-vertex graph is somewhere between $k^n$ and $k(k-1)(dotsb)(k-n+1)$.)
- The graph is bipartite, because $f(2) = 4$ is nonzero.
- When $2$-coloring a bipartite graph, once you color a single vertex, the coloring of its connected component is forced. So the graph must have $2$ connected components, because there are $2^2 = 4$ $2$-colorings.
From here, you only have a few possibilities. Brute force is not out of the question. (And you don't have to try every possibility for brute force to work: if you try a graph $G$ and it has too few colorings, then you know that adding edges to $G$ can't help. Same with removing edges from a graph with too many colorings.) But there are still more things you can figure out from other values of $f$.
For example: when you $3$-color a graph with two connected components, you expect a factor of $3!$ from each component (by permuting the colors used on it). But $f(3) = 90$ is not divisible by $3!^2 = 36$. What does that tell you about the components?
answered Dec 4 '18 at 22:44
Misha LavrovMisha Lavrov
47k657107
$endgroup$
2
$begingroup$
Some other useful facts: the chromatic polynomial of a graph is the product of the chromatic polynomials of its connected components, so if you can factor the chromatic polynomial, you get some more useful information. The coefficient of the next-to-leading term is the negative of the number of edges. The coefficient of the third-highest power relates to the number of triangles, math.stackexchange.com/questions/1636062/…
$endgroup$
– Gerry Myerson
Dec 4 '18 at 23:12
$begingroup$
Why is degree of chromatic polynomial of a n-vertex graph, n?
$endgroup$
– nafhgood
Dec 4 '18 at 23:47
1
$begingroup$
@mathnoob Because the upper and lower bounds on the chromatic polynomial (which I gave in my answer, and which come from the empty graph and the complete graph respectively) are both degree $n$. If the chromatic polynomial of an $n$-vertex graph did not have degree $n$, then it would not stay between those bounds for large $k$.
$endgroup$
– Misha Lavrov
Dec 4 '18 at 23:49
2
$begingroup$
Or to put it differently: for extremely large $k$, the number of ways to $k$-color an $n$-vertex graph should be about $k^n$, because we have $n$ choices with about $k$ options for each.
$endgroup$
– Misha Lavrov
Dec 4 '18 at 23:51
2
$begingroup$
@GerryMyerson There's also the formula as a sum over partitions into independent sets: one partition is always the one into $n$ singletons, which contributes a degree $n$ term, and the rest contribute lower-order terms.
$endgroup$
– Misha Lavrov
Dec 5 '18 at 5:58
|
show 1 more comment
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3026262%2ffinding-a-graph-given-a-chromatic-polynomial%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Let's look at the things we can figure out easily:
- The graph has $6$ vertices, because the polynomial has degree $6$. (In general, the chromatic polynomial of an $n$-vertex graph is somewhere between $k^n$ and $k(k-1)(dotsb)(k-n+1)$.)
- The graph is bipartite, because $f(2) = 4$ is nonzero.
- When $2$-coloring a bipartite graph, once you color a single vertex, the coloring of its connected component is forced. So the graph must have $2$ connected components, because there are $2^2 = 4$ $2$-colorings.
From here, you only have a few possibilities. Brute force is not out of the question. (And you don't have to try every possibility for brute force to work: if you try a graph $G$ and it has too few colorings, then you know that adding edges to $G$ can't help. Same with removing edges from a graph with too many colorings.) But there are still more things you can figure out from other values of $f$.
For example: when you $3$-color a graph with two connected components, you expect a factor of $3!$ from each component (by permuting the colors used on it). But $f(3) = 90$ is not divisible by $3!^2 = 36$. What does that tell you about the components?
answered Dec 4 '18 at 22:44
Misha LavrovMisha Lavrov
47k657107
$endgroup$
2
$begingroup$
Some other useful facts: the chromatic polynomial of a graph is the product of the chromatic polynomials of its connected components, so if you can factor the chromatic polynomial, you get some more useful information. The coefficient of the next-to-leading term is the negative of the number of edges. The coefficient of the third-highest power relates to the number of triangles, math.stackexchange.com/questions/1636062/…
$endgroup$
– Gerry Myerson
Dec 4 '18 at 23:12
$begingroup$
Why is degree of chromatic polynomial of a n-vertex graph, n?
$endgroup$
– nafhgood
Dec 4 '18 at 23:47
1
$begingroup$
@mathnoob Because the upper and lower bounds on the chromatic polynomial (which I gave in my answer, and which come from the empty graph and the complete graph respectively) are both degree $n$. If the chromatic polynomial of an $n$-vertex graph did not have degree $n$, then it would not stay between those bounds for large $k$.
$endgroup$
– Misha Lavrov
Dec 4 '18 at 23:49
2
$begingroup$
Or to put it differently: for extremely large $k$, the number of ways to $k$-color an $n$-vertex graph should be about $k^n$, because we have $n$ choices with about $k$ options for each.
$endgroup$
– Misha Lavrov
Dec 4 '18 at 23:51
2
$begingroup$
@GerryMyerson There's also the formula as a sum over partitions into independent sets: one partition is always the one into $n$ singletons, which contributes a degree $n$ term, and the rest contribute lower-order terms.
$endgroup$
– Misha Lavrov
Dec 5 '18 at 5:58
|
show 1 more comment
$begingroup$
Let's look at the things we can figure out easily:
- The graph has $6$ vertices, because the polynomial has degree $6$. (In general, the chromatic polynomial of an $n$-vertex graph is somewhere between $k^n$ and $k(k-1)(dotsb)(k-n+1)$.)
- The graph is bipartite, because $f(2) = 4$ is nonzero.
- When $2$-coloring a bipartite graph, once you color a single vertex, the coloring of its connected component is forced. So the graph must have $2$ connected components, because there are $2^2 = 4$ $2$-colorings.
From here, you only have a few possibilities. Brute force is not out of the question. (And you don't have to try every possibility for brute force to work: if you try a graph $G$ and it has too few colorings, then you know that adding edges to $G$ can't help. Same with removing edges from a graph with too many colorings.) But there are still more things you can figure out from other values of $f$.
For example: when you $3$-color a graph with two connected components, you expect a factor of $3!$ from each component (by permuting the colors used on it). But $f(3) = 90$ is not divisible by $3!^2 = 36$. What does that tell you about the components?
answered Dec 4 '18 at 22:44
Misha LavrovMisha Lavrov
47k657107
$endgroup$
2
$begingroup$
Some other useful facts: the chromatic polynomial of a graph is the product of the chromatic polynomials of its connected components, so if you can factor the chromatic polynomial, you get some more useful information. The coefficient of the next-to-leading term is the negative of the number of edges. The coefficient of the third-highest power relates to the number of triangles, math.stackexchange.com/questions/1636062/…
$endgroup$
– Gerry Myerson
Dec 4 '18 at 23:12
$begingroup$
Why is degree of chromatic polynomial of a n-vertex graph, n?
$endgroup$
– nafhgood
Dec 4 '18 at 23:47
1
$begingroup$
@mathnoob Because the upper and lower bounds on the chromatic polynomial (which I gave in my answer, and which come from the empty graph and the complete graph respectively) are both degree $n$. If the chromatic polynomial of an $n$-vertex graph did not have degree $n$, then it would not stay between those bounds for large $k$.
$endgroup$
– Misha Lavrov
Dec 4 '18 at 23:49
2
$begingroup$
Or to put it differently: for extremely large $k$, the number of ways to $k$-color an $n$-vertex graph should be about $k^n$, because we have $n$ choices with about $k$ options for each.
$endgroup$
– Misha Lavrov
Dec 4 '18 at 23:51
2
$begingroup$
@GerryMyerson There's also the formula as a sum over partitions into independent sets: one partition is always the one into $n$ singletons, which contributes a degree $n$ term, and the rest contribute lower-order terms.
$endgroup$
– Misha Lavrov
Dec 5 '18 at 5:58
|
show 1 more comment
$begingroup$
Let's look at the things we can figure out easily:
- The graph has $6$ vertices, because the polynomial has degree $6$. (In general, the chromatic polynomial of an $n$-vertex graph is somewhere between $k^n$ and $k(k-1)(dotsb)(k-n+1)$.)
- The graph is bipartite, because $f(2) = 4$ is nonzero.
- When $2$-coloring a bipartite graph, once you color a single vertex, the coloring of its connected component is forced. So the graph must have $2$ connected components, because there are $2^2 = 4$ $2$-colorings.
From here, you only have a few possibilities. Brute force is not out of the question. (And you don't have to try every possibility for brute force to work: if you try a graph $G$ and it has too few colorings, then you know that adding edges to $G$ can't help. Same with removing edges from a graph with too many colorings.) But there are still more things you can figure out from other values of $f$.
For example: when you $3$-color a graph with two connected components, you expect a factor of $3!$ from each component (by permuting the colors used on it). But $f(3) = 90$ is not divisible by $3!^2 = 36$. What does that tell you about the components?
answered Dec 4 '18 at 22:44
Misha LavrovMisha Lavrov
47k657107
$endgroup$
Let's look at the things we can figure out easily:
- The graph has $6$ vertices, because the polynomial has degree $6$. (In general, the chromatic polynomial of an $n$-vertex graph is somewhere between $k^n$ and $k(k-1)(dotsb)(k-n+1)$.)
- The graph is bipartite, because $f(2) = 4$ is nonzero.
- When $2$-coloring a bipartite graph, once you color a single vertex, the coloring of its connected component is forced. So the graph must have $2$ connected components, because there are $2^2 = 4$ $2$-colorings.
From here, you only have a few possibilities. Brute force is not out of the question. (And you don't have to try every possibility for brute force to work: if you try a graph $G$ and it has too few colorings, then you know that adding edges to $G$ can't help. Same with removing edges from a graph with too many colorings.) But there are still more things you can figure out from other values of $f$.
For example: when you $3$-color a graph with two connected components, you expect a factor of $3!$ from each component (by permuting the colors used on it). But $f(3) = 90$ is not divisible by $3!^2 = 36$. What does that tell you about the components?
answered Dec 4 '18 at 22:44
Misha LavrovMisha Lavrov
47k657107
answered Dec 4 '18 at 22:44
Misha LavrovMisha Lavrov
47k657107
answered Dec 4 '18 at 22:44
Misha LavrovMisha Lavrov
47k657107
answered Dec 4 '18 at 22:44
Misha LavrovMisha Lavrov
47k657107
47k657107
2
$begingroup$
Some other useful facts: the chromatic polynomial of a graph is the product of the chromatic polynomials of its connected components, so if you can factor the chromatic polynomial, you get some more useful information. The coefficient of the next-to-leading term is the negative of the number of edges. The coefficient of the third-highest power relates to the number of triangles, math.stackexchange.com/questions/1636062/…
$endgroup$
– Gerry Myerson
Dec 4 '18 at 23:12
$begingroup$
Why is degree of chromatic polynomial of a n-vertex graph, n?
$endgroup$
– nafhgood
Dec 4 '18 at 23:47
1
$begingroup$
@mathnoob Because the upper and lower bounds on the chromatic polynomial (which I gave in my answer, and which come from the empty graph and the complete graph respectively) are both degree $n$. If the chromatic polynomial of an $n$-vertex graph did not have degree $n$, then it would not stay between those bounds for large $k$.
$endgroup$
– Misha Lavrov
Dec 4 '18 at 23:49
2
$begingroup$
Or to put it differently: for extremely large $k$, the number of ways to $k$-color an $n$-vertex graph should be about $k^n$, because we have $n$ choices with about $k$ options for each.
$endgroup$
– Misha Lavrov
Dec 4 '18 at 23:51
2
$begingroup$
@GerryMyerson There's also the formula as a sum over partitions into independent sets: one partition is always the one into $n$ singletons, which contributes a degree $n$ term, and the rest contribute lower-order terms.
$endgroup$
– Misha Lavrov
Dec 5 '18 at 5:58
|
show 1 more comment
2
$begingroup$
Some other useful facts: the chromatic polynomial of a graph is the product of the chromatic polynomials of its connected components, so if you can factor the chromatic polynomial, you get some more useful information. The coefficient of the next-to-leading term is the negative of the number of edges. The coefficient of the third-highest power relates to the number of triangles, math.stackexchange.com/questions/1636062/…
$endgroup$
– Gerry Myerson
Dec 4 '18 at 23:12
$begingroup$
Why is degree of chromatic polynomial of a n-vertex graph, n?
$endgroup$
– nafhgood
Dec 4 '18 at 23:47
1
$begingroup$
@mathnoob Because the upper and lower bounds on the chromatic polynomial (which I gave in my answer, and which come from the empty graph and the complete graph respectively) are both degree $n$. If the chromatic polynomial of an $n$-vertex graph did not have degree $n$, then it would not stay between those bounds for large $k$.
$endgroup$
– Misha Lavrov
Dec 4 '18 at 23:49
2
$begingroup$
Or to put it differently: for extremely large $k$, the number of ways to $k$-color an $n$-vertex graph should be about $k^n$, because we have $n$ choices with about $k$ options for each.
$endgroup$
– Misha Lavrov
Dec 4 '18 at 23:51
2
$begingroup$
@GerryMyerson There's also the formula as a sum over partitions into independent sets: one partition is always the one into $n$ singletons, which contributes a degree $n$ term, and the rest contribute lower-order terms.
$endgroup$
– Misha Lavrov
Dec 5 '18 at 5:58
2
2
$begingroup$
Some other useful facts: the chromatic polynomial of a graph is the product of the chromatic polynomials of its connected components, so if you can factor the chromatic polynomial, you get some more useful information. The coefficient of the next-to-leading term is the negative of the number of edges. The coefficient of the third-highest power relates to the number of triangles, math.stackexchange.com/questions/1636062/…
$endgroup$
– Gerry Myerson
Dec 4 '18 at 23:12
$begingroup$
Some other useful facts: the chromatic polynomial of a graph is the product of the chromatic polynomials of its connected components, so if you can factor the chromatic polynomial, you get some more useful information. The coefficient of the next-to-leading term is the negative of the number of edges. The coefficient of the third-highest power relates to the number of triangles, math.stackexchange.com/questions/1636062/…
$endgroup$
– Gerry Myerson
Dec 4 '18 at 23:12
$begingroup$
Why is degree of chromatic polynomial of a n-vertex graph, n?
$endgroup$
– nafhgood
Dec 4 '18 at 23:47
$begingroup$
Why is degree of chromatic polynomial of a n-vertex graph, n?
$endgroup$
– nafhgood
Dec 4 '18 at 23:47
1
1
$begingroup$
@mathnoob Because the upper and lower bounds on the chromatic polynomial (which I gave in my answer, and which come from the empty graph and the complete graph respectively) are both degree $n$. If the chromatic polynomial of an $n$-vertex graph did not have degree $n$, then it would not stay between those bounds for large $k$.
$endgroup$
– Misha Lavrov
Dec 4 '18 at 23:49
$begingroup$
@mathnoob Because the upper and lower bounds on the chromatic polynomial (which I gave in my answer, and which come from the empty graph and the complete graph respectively) are both degree $n$. If the chromatic polynomial of an $n$-vertex graph did not have degree $n$, then it would not stay between those bounds for large $k$.
$endgroup$
– Misha Lavrov
Dec 4 '18 at 23:49
2
2
$begingroup$
Or to put it differently: for extremely large $k$, the number of ways to $k$-color an $n$-vertex graph should be about $k^n$, because we have $n$ choices with about $k$ options for each.
$endgroup$
– Misha Lavrov
Dec 4 '18 at 23:51
$begingroup$
Or to put it differently: for extremely large $k$, the number of ways to $k$-color an $n$-vertex graph should be about $k^n$, because we have $n$ choices with about $k$ options for each.
$endgroup$
– Misha Lavrov
Dec 4 '18 at 23:51
2
2
$begingroup$
@GerryMyerson There's also the formula as a sum over partitions into independent sets: one partition is always the one into $n$ singletons, which contributes a degree $n$ term, and the rest contribute lower-order terms.
$endgroup$
– Misha Lavrov
Dec 5 '18 at 5:58
$begingroup$
@GerryMyerson There's also the formula as a sum over partitions into independent sets: one partition is always the one into $n$ singletons, which contributes a degree $n$ term, and the rest contribute lower-order terms.
$endgroup$
– Misha Lavrov
Dec 5 '18 at 5:58
|
show 1 more comment
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3026262%2ffinding-a-graph-given-a-chromatic-polynomial%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
