Is right this chromatic polynomial for this Bridge Graph?
I have the following graph:
Bridge Graph with N = 8
And I need to find its chromatic polynomial.
Based in my notes, I have reached the following result:
$$Pg(x) = frac{((x-1)^4 + (x-1))^2}{x(x-1)} $$.
It is because I have applied this formula:
$$Pg(x) = frac{Pg1(x) Pg2(x)}{Pkr(x)} $$.
Taking the Bridge Graph and the previous formula, I have replaced with:
$$ Pg1(x) = Pg2(x) = Pc4(x)= (x-1)^4+(x-1) $$
Because both sub-graphs are cycles.
On the other hand, the Pkr(x) in this case is equals to Pk2(x). So, the chromatic polynomial for a complete graph with n = 2, could be expressed as :
$$x(x-1)$$
So, my main doubt is if this reasoning is right. Because I'm not sure about my resolution and I think that Ia have missing something in the final response.
Thanks a lot!
graph-theory coloring
asked yesterday
BrunoBern
102
add a comment |
I have the following graph:
Bridge Graph with N = 8
And I need to find its chromatic polynomial.
Based in my notes, I have reached the following result:
$$Pg(x) = frac{((x-1)^4 + (x-1))^2}{x(x-1)} $$.
It is because I have applied this formula:
$$Pg(x) = frac{Pg1(x) Pg2(x)}{Pkr(x)} $$.
Taking the Bridge Graph and the previous formula, I have replaced with:
$$ Pg1(x) = Pg2(x) = Pc4(x)= (x-1)^4+(x-1) $$
Because both sub-graphs are cycles.
On the other hand, the Pkr(x) in this case is equals to Pk2(x). So, the chromatic polynomial for a complete graph with n = 2, could be expressed as :
$$x(x-1)$$
So, my main doubt is if this reasoning is right. Because I'm not sure about my resolution and I think that Ia have missing something in the final response.
Thanks a lot!
graph-theory coloring
asked yesterday
BrunoBern
102
add a comment |
I have the following graph:
Bridge Graph with N = 8
And I need to find its chromatic polynomial.
Based in my notes, I have reached the following result:
$$Pg(x) = frac{((x-1)^4 + (x-1))^2}{x(x-1)} $$.
It is because I have applied this formula:
$$Pg(x) = frac{Pg1(x) Pg2(x)}{Pkr(x)} $$.
Taking the Bridge Graph and the previous formula, I have replaced with:
$$ Pg1(x) = Pg2(x) = Pc4(x)= (x-1)^4+(x-1) $$
Because both sub-graphs are cycles.
On the other hand, the Pkr(x) in this case is equals to Pk2(x). So, the chromatic polynomial for a complete graph with n = 2, could be expressed as :
$$x(x-1)$$
So, my main doubt is if this reasoning is right. Because I'm not sure about my resolution and I think that Ia have missing something in the final response.
Thanks a lot!
graph-theory coloring
asked yesterday
BrunoBern
102
I have the following graph:
Bridge Graph with N = 8
And I need to find its chromatic polynomial.
Based in my notes, I have reached the following result:
$$Pg(x) = frac{((x-1)^4 + (x-1))^2}{x(x-1)} $$.
It is because I have applied this formula:
$$Pg(x) = frac{Pg1(x) Pg2(x)}{Pkr(x)} $$.
Taking the Bridge Graph and the previous formula, I have replaced with:
$$ Pg1(x) = Pg2(x) = Pc4(x)= (x-1)^4+(x-1) $$
Because both sub-graphs are cycles.
On the other hand, the Pkr(x) in this case is equals to Pk2(x). So, the chromatic polynomial for a complete graph with n = 2, could be expressed as :
$$x(x-1)$$
So, my main doubt is if this reasoning is right. Because I'm not sure about my resolution and I think that Ia have missing something in the final response.
Thanks a lot!
graph-theory coloring
graph-theory coloring
asked yesterday
BrunoBern
102
asked yesterday
BrunoBern
102
asked yesterday
BrunoBern
102
asked yesterday
BrunoBern
102
asked yesterday
BrunoBern
102
102
add a comment |
add a comment |
2 Answers
2
active
oldest
votes
The formula
$$
P_G(x) = frac{P_{G_1}(x) cdot P_{G_2}(x)}{P_{K_r}(x)}
$$
that you are using is appropriate when $G$ is the clique sum of the graphs $G_1$ and $G_2$ along a copy of $K_r$.
The graph you give,
is not a clique sum of two cycles. Instead, it is a clique sum (along a $K_2$) of the graph induced by vertices ${a,b,c,d,e}$ and the graph induced by vertices ${d,e,f,g,h}$.
Both of these are not cycles, but cycles with an extra leaf vertex. Here is how we deal with that extra vertex. If the cycle has chromatic number $(x-1)^4+(x-1)$, then there are always $x-1$ ways to color the leaf vertex with a color different from its only neighbor, so in this case we have $P_{G_1}(x) = P_{G_2}(x) = (x-1)^5 + (x-1)^2$.
Applying the formula, we get
$$
P_G(x) = frac{[(x-1)^5 + (x-1)^2]^2}{x(x-1)} = x^8-9 x^7+36 x^6-82 x^5+114 x^4-96 x^3+45 x^2-9 x.
$$
(A quick sanity check which this result passes and yours does not is that the degree of $P_G(x)$ must be the number of vertices in $G$.)
answered yesterday
Misha Lavrov
44k555106
add a comment |
Using standard techniques:
$$x^8-9 x^7+36 x^6-82 x^5+114 x^4-96 x^3+45 x^2-9 x$$
answered yesterday
David G. Stork
9,93521232
add a 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%2f3062333%2fis-right-this-chromatic-polynomial-for-this-bridge-graph%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
The formula
$$
P_G(x) = frac{P_{G_1}(x) cdot P_{G_2}(x)}{P_{K_r}(x)}
$$
that you are using is appropriate when $G$ is the clique sum of the graphs $G_1$ and $G_2$ along a copy of $K_r$.
The graph you give,
is not a clique sum of two cycles. Instead, it is a clique sum (along a $K_2$) of the graph induced by vertices ${a,b,c,d,e}$ and the graph induced by vertices ${d,e,f,g,h}$.
Both of these are not cycles, but cycles with an extra leaf vertex. Here is how we deal with that extra vertex. If the cycle has chromatic number $(x-1)^4+(x-1)$, then there are always $x-1$ ways to color the leaf vertex with a color different from its only neighbor, so in this case we have $P_{G_1}(x) = P_{G_2}(x) = (x-1)^5 + (x-1)^2$.
Applying the formula, we get
$$
P_G(x) = frac{[(x-1)^5 + (x-1)^2]^2}{x(x-1)} = x^8-9 x^7+36 x^6-82 x^5+114 x^4-96 x^3+45 x^2-9 x.
$$
(A quick sanity check which this result passes and yours does not is that the degree of $P_G(x)$ must be the number of vertices in $G$.)
answered yesterday
Misha Lavrov
44k555106
add a comment |
The formula
$$
P_G(x) = frac{P_{G_1}(x) cdot P_{G_2}(x)}{P_{K_r}(x)}
$$
that you are using is appropriate when $G$ is the clique sum of the graphs $G_1$ and $G_2$ along a copy of $K_r$.
The graph you give,
is not a clique sum of two cycles. Instead, it is a clique sum (along a $K_2$) of the graph induced by vertices ${a,b,c,d,e}$ and the graph induced by vertices ${d,e,f,g,h}$.
Both of these are not cycles, but cycles with an extra leaf vertex. Here is how we deal with that extra vertex. If the cycle has chromatic number $(x-1)^4+(x-1)$, then there are always $x-1$ ways to color the leaf vertex with a color different from its only neighbor, so in this case we have $P_{G_1}(x) = P_{G_2}(x) = (x-1)^5 + (x-1)^2$.
Applying the formula, we get
$$
P_G(x) = frac{[(x-1)^5 + (x-1)^2]^2}{x(x-1)} = x^8-9 x^7+36 x^6-82 x^5+114 x^4-96 x^3+45 x^2-9 x.
$$
(A quick sanity check which this result passes and yours does not is that the degree of $P_G(x)$ must be the number of vertices in $G$.)
answered yesterday
Misha Lavrov
44k555106
add a comment |
The formula
$$
P_G(x) = frac{P_{G_1}(x) cdot P_{G_2}(x)}{P_{K_r}(x)}
$$
that you are using is appropriate when $G$ is the clique sum of the graphs $G_1$ and $G_2$ along a copy of $K_r$.
The graph you give,
is not a clique sum of two cycles. Instead, it is a clique sum (along a $K_2$) of the graph induced by vertices ${a,b,c,d,e}$ and the graph induced by vertices ${d,e,f,g,h}$.
Both of these are not cycles, but cycles with an extra leaf vertex. Here is how we deal with that extra vertex. If the cycle has chromatic number $(x-1)^4+(x-1)$, then there are always $x-1$ ways to color the leaf vertex with a color different from its only neighbor, so in this case we have $P_{G_1}(x) = P_{G_2}(x) = (x-1)^5 + (x-1)^2$.
Applying the formula, we get
$$
P_G(x) = frac{[(x-1)^5 + (x-1)^2]^2}{x(x-1)} = x^8-9 x^7+36 x^6-82 x^5+114 x^4-96 x^3+45 x^2-9 x.
$$
(A quick sanity check which this result passes and yours does not is that the degree of $P_G(x)$ must be the number of vertices in $G$.)
answered yesterday
Misha Lavrov
44k555106
The formula
$$
P_G(x) = frac{P_{G_1}(x) cdot P_{G_2}(x)}{P_{K_r}(x)}
$$
that you are using is appropriate when $G$ is the clique sum of the graphs $G_1$ and $G_2$ along a copy of $K_r$.
The graph you give,
is not a clique sum of two cycles. Instead, it is a clique sum (along a $K_2$) of the graph induced by vertices ${a,b,c,d,e}$ and the graph induced by vertices ${d,e,f,g,h}$.
Both of these are not cycles, but cycles with an extra leaf vertex. Here is how we deal with that extra vertex. If the cycle has chromatic number $(x-1)^4+(x-1)$, then there are always $x-1$ ways to color the leaf vertex with a color different from its only neighbor, so in this case we have $P_{G_1}(x) = P_{G_2}(x) = (x-1)^5 + (x-1)^2$.
Applying the formula, we get
$$
P_G(x) = frac{[(x-1)^5 + (x-1)^2]^2}{x(x-1)} = x^8-9 x^7+36 x^6-82 x^5+114 x^4-96 x^3+45 x^2-9 x.
$$
(A quick sanity check which this result passes and yours does not is that the degree of $P_G(x)$ must be the number of vertices in $G$.)
answered yesterday
Misha Lavrov
44k555106
edited yesterday
answered yesterday
Misha Lavrov
44k555106
answered yesterday
Misha Lavrov
44k555106
answered yesterday
Misha Lavrov
44k555106
44k555106
add a comment |
add a comment |
Using standard techniques:
$$x^8-9 x^7+36 x^6-82 x^5+114 x^4-96 x^3+45 x^2-9 x$$
answered yesterday
David G. Stork
9,93521232
add a comment |
Using standard techniques:
$$x^8-9 x^7+36 x^6-82 x^5+114 x^4-96 x^3+45 x^2-9 x$$
answered yesterday
David G. Stork
9,93521232
add a comment |
Using standard techniques:
$$x^8-9 x^7+36 x^6-82 x^5+114 x^4-96 x^3+45 x^2-9 x$$
answered yesterday
David G. Stork
9,93521232
Using standard techniques:
$$x^8-9 x^7+36 x^6-82 x^5+114 x^4-96 x^3+45 x^2-9 x$$
answered yesterday
David G. Stork
9,93521232
edited yesterday
answered yesterday
David G. Stork
9,93521232
answered yesterday
David G. Stork
9,93521232
answered yesterday
David G. Stork
9,93521232
9,93521232
add a comment |
add a 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.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- 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.
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%2f3062333%2fis-right-this-chromatic-polynomial-for-this-bridge-graph%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
