Mixing
A new graph invariant? The maximum number of non-equivalent colorings with $n$ colors.
7
$begingroup$
Consider (proper) coloring of a finite graph $G$ with exactly $n$ colors and the following coloring transformation: choose an edge of the graph with the end nodes of colors $a$ and $b$ and swap the colors $a$ and $b$ in the connected component of the graph, containing the edge and colored with the two colors. The result is new (proper) coloring of the graph. Lets call two colorings equivalent if there is a sequence of the swaps taking one graph coloring into another. Let $C_n(G)$ be a maximum number of non-equivalent colorings of the graph $G$ with $n$ colors (number of equivalence classes).
QUESTIONS:
- Is $C_n(G)$ a new graph invariant or it can be calculated from the chromatic polynomial of the graph $G$?
- Is there efficient way to calculate $C_n(G)$?
- Could $C_n(G)$ be a complete graph invariant, considering it for all natural numbers $n$?
NOTE:
For the non-triviality and the origin of $C_n(G)$, please, see On the four and five color theorems
graph-theory coloring planar-graph invariant-theory invariance
edited Jan 14 at 5:55
Blue
48.4k870154
asked Jan 14 at 3:38
DVDDVD
532425
$endgroup$
|
show 2 more comments
7
$begingroup$
Consider (proper) coloring of a finite graph $G$ with exactly $n$ colors and the following coloring transformation: choose an edge of the graph with the end nodes of colors $a$ and $b$ and swap the colors $a$ and $b$ in the connected component of the graph, containing the edge and colored with the two colors. The result is new (proper) coloring of the graph. Lets call two colorings equivalent if there is a sequence of the swaps taking one graph coloring into another. Let $C_n(G)$ be a maximum number of non-equivalent colorings of the graph $G$ with $n$ colors (number of equivalence classes).
QUESTIONS:
- Is $C_n(G)$ a new graph invariant or it can be calculated from the chromatic polynomial of the graph $G$?
- Is there efficient way to calculate $C_n(G)$?
- Could $C_n(G)$ be a complete graph invariant, considering it for all natural numbers $n$?
NOTE:
For the non-triviality and the origin of $C_n(G)$, please, see On the four and five color theorems
graph-theory coloring planar-graph invariant-theory invariance
edited Jan 14 at 5:55
Blue
48.4k870154
asked Jan 14 at 3:38
DVDDVD
532425
$endgroup$
$begingroup$
The number of vertex-colorings of $G$ using exactly $n$ colors can be derived from the chromatic polynomial of $G$, and (at least in the connected case) $C_n(G)$ is just that modulo an extra factor of $1/n!$. The chromatic polynomial is not a complete graph invariant.
$endgroup$
– anomaly
Jan 14 at 4:12
1
$begingroup$
@anomaly Why would $C_n(G)$ be the number of $n$-colorings divided by $n!$? There are colorings which are equivalent, but are not obtained from each other just by permuting the colors.
$endgroup$
– Misha Lavrov
Jan 14 at 4:16
$begingroup$
@MishaLavrov: I thought equivalence is a type of permutation, at least within a connected component. The OP said to swap the colors a and b. The only restriction seems to be that $a$ and $b$ have to share an edge to allow the permutation to be legal.
$endgroup$
– Cheerful Parsnip
Jan 14 at 4:21
1
$begingroup$
@CheerfulParsnip As I understand it, we only swap the colors $a$ and $b$ on the connected component of the subgraph induced by those colors. So the colors $a$ and $b$ get swapped in parts of the graph, but not others, even if the graph as a whole is connected. If we take the other interpretation, the question is trivial.
$endgroup$
– Misha Lavrov
Jan 14 at 4:23
$begingroup$
@MishaLavrov: Is the swap in the connected component of $G$ itself, or just in some induced subgraph? I was assuming the former.
$endgroup$
– anomaly
Jan 14 at 4:26
|
show 2 more comments
7
7
7
2
$begingroup$
Consider (proper) coloring of a finite graph $G$ with exactly $n$ colors and the following coloring transformation: choose an edge of the graph with the end nodes of colors $a$ and $b$ and swap the colors $a$ and $b$ in the connected component of the graph, containing the edge and colored with the two colors. The result is new (proper) coloring of the graph. Lets call two colorings equivalent if there is a sequence of the swaps taking one graph coloring into another. Let $C_n(G)$ be a maximum number of non-equivalent colorings of the graph $G$ with $n$ colors (number of equivalence classes).
QUESTIONS:
- Is $C_n(G)$ a new graph invariant or it can be calculated from the chromatic polynomial of the graph $G$?
- Is there efficient way to calculate $C_n(G)$?
- Could $C_n(G)$ be a complete graph invariant, considering it for all natural numbers $n$?
NOTE:
For the non-triviality and the origin of $C_n(G)$, please, see On the four and five color theorems
graph-theory coloring planar-graph invariant-theory invariance
edited Jan 14 at 5:55
Blue
48.4k870154
asked Jan 14 at 3:38
DVDDVD
532425
$endgroup$
Consider (proper) coloring of a finite graph $G$ with exactly $n$ colors and the following coloring transformation: choose an edge of the graph with the end nodes of colors $a$ and $b$ and swap the colors $a$ and $b$ in the connected component of the graph, containing the edge and colored with the two colors. The result is new (proper) coloring of the graph. Lets call two colorings equivalent if there is a sequence of the swaps taking one graph coloring into another. Let $C_n(G)$ be a maximum number of non-equivalent colorings of the graph $G$ with $n$ colors (number of equivalence classes).
QUESTIONS:
- Is $C_n(G)$ a new graph invariant or it can be calculated from the chromatic polynomial of the graph $G$?
- Is there efficient way to calculate $C_n(G)$?
- Could $C_n(G)$ be a complete graph invariant, considering it for all natural numbers $n$?
NOTE:
For the non-triviality and the origin of $C_n(G)$, please, see On the four and five color theorems
graph-theory coloring planar-graph invariant-theory invariance
graph-theory coloring planar-graph invariant-theory invariance
edited Jan 14 at 5:55
Blue
48.4k870154
asked Jan 14 at 3:38
DVDDVD
532425
edited Jan 14 at 5:55
Blue
48.4k870154
asked Jan 14 at 3:38
DVDDVD
532425
edited Jan 14 at 5:55
Blue
48.4k870154
edited Jan 14 at 5:55
Blue
48.4k870154
edited Jan 14 at 5:55
Blue
48.4k870154
48.4k870154
asked Jan 14 at 3:38
DVDDVD
532425
asked Jan 14 at 3:38
DVDDVD
532425
asked Jan 14 at 3:38
DVDDVD
532425
532425
$begingroup$
The number of vertex-colorings of $G$ using exactly $n$ colors can be derived from the chromatic polynomial of $G$, and (at least in the connected case) $C_n(G)$ is just that modulo an extra factor of $1/n!$. The chromatic polynomial is not a complete graph invariant.
$endgroup$
– anomaly
Jan 14 at 4:12
1
$begingroup$
@anomaly Why would $C_n(G)$ be the number of $n$-colorings divided by $n!$? There are colorings which are equivalent, but are not obtained from each other just by permuting the colors.
$endgroup$
– Misha Lavrov
Jan 14 at 4:16
$begingroup$
@MishaLavrov: I thought equivalence is a type of permutation, at least within a connected component. The OP said to swap the colors a and b. The only restriction seems to be that $a$ and $b$ have to share an edge to allow the permutation to be legal.
$endgroup$
– Cheerful Parsnip
Jan 14 at 4:21
1
$begingroup$
@CheerfulParsnip As I understand it, we only swap the colors $a$ and $b$ on the connected component of the subgraph induced by those colors. So the colors $a$ and $b$ get swapped in parts of the graph, but not others, even if the graph as a whole is connected. If we take the other interpretation, the question is trivial.
$endgroup$
– Misha Lavrov
Jan 14 at 4:23
$begingroup$
@MishaLavrov: Is the swap in the connected component of $G$ itself, or just in some induced subgraph? I was assuming the former.
$endgroup$
– anomaly
Jan 14 at 4:26
|
show 2 more comments
$begingroup$
The number of vertex-colorings of $G$ using exactly $n$ colors can be derived from the chromatic polynomial of $G$, and (at least in the connected case) $C_n(G)$ is just that modulo an extra factor of $1/n!$. The chromatic polynomial is not a complete graph invariant.
$endgroup$
– anomaly
Jan 14 at 4:12
1
$begingroup$
@anomaly Why would $C_n(G)$ be the number of $n$-colorings divided by $n!$? There are colorings which are equivalent, but are not obtained from each other just by permuting the colors.
$endgroup$
– Misha Lavrov
Jan 14 at 4:16
$begingroup$
@MishaLavrov: I thought equivalence is a type of permutation, at least within a connected component. The OP said to swap the colors a and b. The only restriction seems to be that $a$ and $b$ have to share an edge to allow the permutation to be legal.
$endgroup$
– Cheerful Parsnip
Jan 14 at 4:21
1
$begingroup$
@CheerfulParsnip As I understand it, we only swap the colors $a$ and $b$ on the connected component of the subgraph induced by those colors. So the colors $a$ and $b$ get swapped in parts of the graph, but not others, even if the graph as a whole is connected. If we take the other interpretation, the question is trivial.
$endgroup$
– Misha Lavrov
Jan 14 at 4:23
$begingroup$
@MishaLavrov: Is the swap in the connected component of $G$ itself, or just in some induced subgraph? I was assuming the former.
$endgroup$
– anomaly
Jan 14 at 4:26
$begingroup$
The number of vertex-colorings of $G$ using exactly $n$ colors can be derived from the chromatic polynomial of $G$, and (at least in the connected case) $C_n(G)$ is just that modulo an extra factor of $1/n!$. The chromatic polynomial is not a complete graph invariant.
$endgroup$
– anomaly
Jan 14 at 4:12
$begingroup$
The number of vertex-colorings of $G$ using exactly $n$ colors can be derived from the chromatic polynomial of $G$, and (at least in the connected case) $C_n(G)$ is just that modulo an extra factor of $1/n!$. The chromatic polynomial is not a complete graph invariant.
$endgroup$
– anomaly
Jan 14 at 4:12
1
1
$begingroup$
@anomaly Why would $C_n(G)$ be the number of $n$-colorings divided by $n!$? There are colorings which are equivalent, but are not obtained from each other just by permuting the colors.
$endgroup$
– Misha Lavrov
Jan 14 at 4:16
$begingroup$
@anomaly Why would $C_n(G)$ be the number of $n$-colorings divided by $n!$? There are colorings which are equivalent, but are not obtained from each other just by permuting the colors.
$endgroup$
– Misha Lavrov
Jan 14 at 4:16
$begingroup$
@MishaLavrov: I thought equivalence is a type of permutation, at least within a connected component. The OP said to swap the colors a and b. The only restriction seems to be that $a$ and $b$ have to share an edge to allow the permutation to be legal.
$endgroup$
– Cheerful Parsnip
Jan 14 at 4:21
$begingroup$
@MishaLavrov: I thought equivalence is a type of permutation, at least within a connected component. The OP said to swap the colors a and b. The only restriction seems to be that $a$ and $b$ have to share an edge to allow the permutation to be legal.
$endgroup$
– Cheerful Parsnip
Jan 14 at 4:21
1
1
$begingroup$
@CheerfulParsnip As I understand it, we only swap the colors $a$ and $b$ on the connected component of the subgraph induced by those colors. So the colors $a$ and $b$ get swapped in parts of the graph, but not others, even if the graph as a whole is connected. If we take the other interpretation, the question is trivial.
$endgroup$
– Misha Lavrov
Jan 14 at 4:23
$begingroup$
@CheerfulParsnip As I understand it, we only swap the colors $a$ and $b$ on the connected component of the subgraph induced by those colors. So the colors $a$ and $b$ get swapped in parts of the graph, but not others, even if the graph as a whole is connected. If we take the other interpretation, the question is trivial.
$endgroup$
– Misha Lavrov
Jan 14 at 4:23
$begingroup$
@MishaLavrov: Is the swap in the connected component of $G$ itself, or just in some induced subgraph? I was assuming the former.
$endgroup$
– anomaly
Jan 14 at 4:26
$begingroup$
@MishaLavrov: Is the swap in the connected component of $G$ itself, or just in some induced subgraph? I was assuming the former.
$endgroup$
– anomaly
Jan 14 at 4:26
|
show 2 more comments
1 Answer
1
active
oldest
votes
1
$begingroup$
The sequence $C_n(G)$ is not a complete graph invariant. It fails to distinguish the bowtie graph (left) from the kite graph (right):
(I picked these two graphs to try based on their use in this paper.)
For both graphs, $C_3(G) = C_4(G) = C_5(G) = 1$ while $C_n(G) = 0$ for all other $n$.
answered Jan 15 at 2:05
Misha LavrovMisha Lavrov
46.3k656107
$endgroup$
$begingroup$
What if we attach its diameter to every equivalence class of colorings for the invariant? That is, $D_n^k$ = the maximum number of swaps between $k$th equivalent coloring class of $n$ colors. Then I get, that $D_4^1(bowtie)=1$ and $D_4^1(kite)=2$, so $D$ distinguishes them. Could this modified invariant be complete?
$endgroup$
– DVD
Jan 17 at 1:31
$begingroup$
It may be useful to add the transformation between colorings that may decrease the number of colors, that is if we have a node with neighbors of few different colors then its color may be changed. For planar graphs it garantees that every coloring is equivalent to a five coloring, please see en.wikipedia.org/wiki/Five_color_theorem.
$endgroup$
– DVD
Jan 17 at 1:48
1
$begingroup$
My intuition is that this sort of thing is unlikely to produce a complete invariant, but likely to make the needed counterexamples more complicated.
$endgroup$
– Misha Lavrov
Jan 17 at 3:43
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
});
}
});
draft saved
draft discarded
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%2f3072826%2fa-new-graph-invariant-the-maximum-number-of-non-equivalent-colorings-with-n-c%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
1
$begingroup$
The sequence $C_n(G)$ is not a complete graph invariant. It fails to distinguish the bowtie graph (left) from the kite graph (right):
(I picked these two graphs to try based on their use in this paper.)
For both graphs, $C_3(G) = C_4(G) = C_5(G) = 1$ while $C_n(G) = 0$ for all other $n$.
answered Jan 15 at 2:05
Misha LavrovMisha Lavrov
46.3k656107
$endgroup$
$begingroup$
What if we attach its diameter to every equivalence class of colorings for the invariant? That is, $D_n^k$ = the maximum number of swaps between $k$th equivalent coloring class of $n$ colors. Then I get, that $D_4^1(bowtie)=1$ and $D_4^1(kite)=2$, so $D$ distinguishes them. Could this modified invariant be complete?
$endgroup$
– DVD
Jan 17 at 1:31
$begingroup$
It may be useful to add the transformation between colorings that may decrease the number of colors, that is if we have a node with neighbors of few different colors then its color may be changed. For planar graphs it garantees that every coloring is equivalent to a five coloring, please see en.wikipedia.org/wiki/Five_color_theorem.
$endgroup$
– DVD
Jan 17 at 1:48
1
$begingroup$
My intuition is that this sort of thing is unlikely to produce a complete invariant, but likely to make the needed counterexamples more complicated.
$endgroup$
– Misha Lavrov
Jan 17 at 3:43
add a comment |
1
$begingroup$
The sequence $C_n(G)$ is not a complete graph invariant. It fails to distinguish the bowtie graph (left) from the kite graph (right):
(I picked these two graphs to try based on their use in this paper.)
For both graphs, $C_3(G) = C_4(G) = C_5(G) = 1$ while $C_n(G) = 0$ for all other $n$.
answered Jan 15 at 2:05
Misha LavrovMisha Lavrov
46.3k656107
$endgroup$
$begingroup$
What if we attach its diameter to every equivalence class of colorings for the invariant? That is, $D_n^k$ = the maximum number of swaps between $k$th equivalent coloring class of $n$ colors. Then I get, that $D_4^1(bowtie)=1$ and $D_4^1(kite)=2$, so $D$ distinguishes them. Could this modified invariant be complete?
$endgroup$
– DVD
Jan 17 at 1:31
$begingroup$
It may be useful to add the transformation between colorings that may decrease the number of colors, that is if we have a node with neighbors of few different colors then its color may be changed. For planar graphs it garantees that every coloring is equivalent to a five coloring, please see en.wikipedia.org/wiki/Five_color_theorem.
$endgroup$
– DVD
Jan 17 at 1:48
1
$begingroup$
My intuition is that this sort of thing is unlikely to produce a complete invariant, but likely to make the needed counterexamples more complicated.
$endgroup$
– Misha Lavrov
Jan 17 at 3:43
add a comment |
1
1
1
$begingroup$
The sequence $C_n(G)$ is not a complete graph invariant. It fails to distinguish the bowtie graph (left) from the kite graph (right):
(I picked these two graphs to try based on their use in this paper.)
For both graphs, $C_3(G) = C_4(G) = C_5(G) = 1$ while $C_n(G) = 0$ for all other $n$.
answered Jan 15 at 2:05
Misha LavrovMisha Lavrov
46.3k656107
$endgroup$
The sequence $C_n(G)$ is not a complete graph invariant. It fails to distinguish the bowtie graph (left) from the kite graph (right):
(I picked these two graphs to try based on their use in this paper.)
For both graphs, $C_3(G) = C_4(G) = C_5(G) = 1$ while $C_n(G) = 0$ for all other $n$.
answered Jan 15 at 2:05
Misha LavrovMisha Lavrov
46.3k656107
answered Jan 15 at 2:05
Misha LavrovMisha Lavrov
46.3k656107
answered Jan 15 at 2:05
Misha LavrovMisha Lavrov
46.3k656107
answered Jan 15 at 2:05
Misha LavrovMisha Lavrov
46.3k656107
46.3k656107
$begingroup$
What if we attach its diameter to every equivalence class of colorings for the invariant? That is, $D_n^k$ = the maximum number of swaps between $k$th equivalent coloring class of $n$ colors. Then I get, that $D_4^1(bowtie)=1$ and $D_4^1(kite)=2$, so $D$ distinguishes them. Could this modified invariant be complete?
$endgroup$
– DVD
Jan 17 at 1:31
$begingroup$
It may be useful to add the transformation between colorings that may decrease the number of colors, that is if we have a node with neighbors of few different colors then its color may be changed. For planar graphs it garantees that every coloring is equivalent to a five coloring, please see en.wikipedia.org/wiki/Five_color_theorem.
$endgroup$
– DVD
Jan 17 at 1:48
1
$begingroup$
My intuition is that this sort of thing is unlikely to produce a complete invariant, but likely to make the needed counterexamples more complicated.
$endgroup$
– Misha Lavrov
Jan 17 at 3:43
add a comment |
$begingroup$
What if we attach its diameter to every equivalence class of colorings for the invariant? That is, $D_n^k$ = the maximum number of swaps between $k$th equivalent coloring class of $n$ colors. Then I get, that $D_4^1(bowtie)=1$ and $D_4^1(kite)=2$, so $D$ distinguishes them. Could this modified invariant be complete?
$endgroup$
– DVD
Jan 17 at 1:31
$begingroup$
It may be useful to add the transformation between colorings that may decrease the number of colors, that is if we have a node with neighbors of few different colors then its color may be changed. For planar graphs it garantees that every coloring is equivalent to a five coloring, please see en.wikipedia.org/wiki/Five_color_theorem.
$endgroup$
– DVD
Jan 17 at 1:48
1
$begingroup$
My intuition is that this sort of thing is unlikely to produce a complete invariant, but likely to make the needed counterexamples more complicated.
$endgroup$
– Misha Lavrov
Jan 17 at 3:43
$begingroup$
What if we attach its diameter to every equivalence class of colorings for the invariant? That is, $D_n^k$ = the maximum number of swaps between $k$th equivalent coloring class of $n$ colors. Then I get, that $D_4^1(bowtie)=1$ and $D_4^1(kite)=2$, so $D$ distinguishes them. Could this modified invariant be complete?
$endgroup$
– DVD
Jan 17 at 1:31
$begingroup$
What if we attach its diameter to every equivalence class of colorings for the invariant? That is, $D_n^k$ = the maximum number of swaps between $k$th equivalent coloring class of $n$ colors. Then I get, that $D_4^1(bowtie)=1$ and $D_4^1(kite)=2$, so $D$ distinguishes them. Could this modified invariant be complete?
$endgroup$
– DVD
Jan 17 at 1:31
$begingroup$
It may be useful to add the transformation between colorings that may decrease the number of colors, that is if we have a node with neighbors of few different colors then its color may be changed. For planar graphs it garantees that every coloring is equivalent to a five coloring, please see en.wikipedia.org/wiki/Five_color_theorem.
$endgroup$
– DVD
Jan 17 at 1:48
$begingroup$
It may be useful to add the transformation between colorings that may decrease the number of colors, that is if we have a node with neighbors of few different colors then its color may be changed. For planar graphs it garantees that every coloring is equivalent to a five coloring, please see en.wikipedia.org/wiki/Five_color_theorem.
$endgroup$
– DVD
Jan 17 at 1:48
1
1
$begingroup$
My intuition is that this sort of thing is unlikely to produce a complete invariant, but likely to make the needed counterexamples more complicated.
$endgroup$
– Misha Lavrov
Jan 17 at 3:43
$begingroup$
My intuition is that this sort of thing is unlikely to produce a complete invariant, but likely to make the needed counterexamples more complicated.
$endgroup$
– Misha Lavrov
Jan 17 at 3:43
add a comment |
draft saved
draft discarded
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.
draft saved
draft discarded
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%2f3072826%2fa-new-graph-invariant-the-maximum-number-of-non-equivalent-colorings-with-n-c%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
$begingroup$
The number of vertex-colorings of $G$ using exactly $n$ colors can be derived from the chromatic polynomial of $G$, and (at least in the connected case) $C_n(G)$ is just that modulo an extra factor of $1/n!$. The chromatic polynomial is not a complete graph invariant.
$endgroup$
– anomaly
Jan 14 at 4:12
1
$begingroup$
@anomaly Why would $C_n(G)$ be the number of $n$-colorings divided by $n!$? There are colorings which are equivalent, but are not obtained from each other just by permuting the colors.
$endgroup$
– Misha Lavrov
Jan 14 at 4:16
$begingroup$
@MishaLavrov: I thought equivalence is a type of permutation, at least within a connected component. The OP said to swap the colors a and b. The only restriction seems to be that $a$ and $b$ have to share an edge to allow the permutation to be legal.
$endgroup$
– Cheerful Parsnip
Jan 14 at 4:21
1
$begingroup$
@CheerfulParsnip As I understand it, we only swap the colors $a$ and $b$ on the connected component of the subgraph induced by those colors. So the colors $a$ and $b$ get swapped in parts of the graph, but not others, even if the graph as a whole is connected. If we take the other interpretation, the question is trivial.
$endgroup$
– Misha Lavrov
Jan 14 at 4:23
$begingroup$
@MishaLavrov: Is the swap in the connected component of $G$ itself, or just in some induced subgraph? I was assuming the former.
$endgroup$
– anomaly
Jan 14 at 4:26