Command to compute the number of $5$-colorings of all $(2k, k^2)$-graphs
$begingroup$
I would like Sage to compute the number of all $5$-colorings of graphs on $2k$ vertices and $k^2$ edges with clique number 3 for a specified $k geq 1$.
I know how to ask call nauty and ask sage to generate, for example, all graphs on $2k=8$ and $k^2=16$ vertices with clique number $3$:
g8 = [g for g in graphs.nauty_geng('8 16') if g.clique_number() == 3]
Is there a way to obtain a list of the number of $5$-colorings of all of these graphs? If not, could I at least obtain their chromatic polynomials? Then I could have them evaluated at $5$.
Thank you in advance for your help.
combinatorics graph-theory math-software programming sagemath
asked Jan 10 at 0:28
SarahSarah
819821
$endgroup$
add a comment |
$begingroup$
I would like Sage to compute the number of all $5$-colorings of graphs on $2k$ vertices and $k^2$ edges with clique number 3 for a specified $k geq 1$.
I know how to ask call nauty and ask sage to generate, for example, all graphs on $2k=8$ and $k^2=16$ vertices with clique number $3$:
g8 = [g for g in graphs.nauty_geng('8 16') if g.clique_number() == 3]
Is there a way to obtain a list of the number of $5$-colorings of all of these graphs? If not, could I at least obtain their chromatic polynomials? Then I could have them evaluated at $5$.
Thank you in advance for your help.
combinatorics graph-theory math-software programming sagemath
asked Jan 10 at 0:28
SarahSarah
819821
$endgroup$
$begingroup$
Well, even for $k=4$ that would seem take a very long time no matter how you try to do it. There would be many such graphs to check, and furthermore, for each such graph many ways to partition the vertices.
$endgroup$
– Mike
Jan 12 at 19:19
add a comment |
$begingroup$
I would like Sage to compute the number of all $5$-colorings of graphs on $2k$ vertices and $k^2$ edges with clique number 3 for a specified $k geq 1$.
I know how to ask call nauty and ask sage to generate, for example, all graphs on $2k=8$ and $k^2=16$ vertices with clique number $3$:
g8 = [g for g in graphs.nauty_geng('8 16') if g.clique_number() == 3]
Is there a way to obtain a list of the number of $5$-colorings of all of these graphs? If not, could I at least obtain their chromatic polynomials? Then I could have them evaluated at $5$.
Thank you in advance for your help.
combinatorics graph-theory math-software programming sagemath
asked Jan 10 at 0:28
SarahSarah
819821
$endgroup$
I would like Sage to compute the number of all $5$-colorings of graphs on $2k$ vertices and $k^2$ edges with clique number 3 for a specified $k geq 1$.
I know how to ask call nauty and ask sage to generate, for example, all graphs on $2k=8$ and $k^2=16$ vertices with clique number $3$:
g8 = [g for g in graphs.nauty_geng('8 16') if g.clique_number() == 3]
Is there a way to obtain a list of the number of $5$-colorings of all of these graphs? If not, could I at least obtain their chromatic polynomials? Then I could have them evaluated at $5$.
Thank you in advance for your help.
combinatorics graph-theory math-software programming sagemath
combinatorics graph-theory math-software programming sagemath
asked Jan 10 at 0:28
SarahSarah
819821
asked Jan 10 at 0:28
SarahSarah
819821
asked Jan 10 at 0:28
SarahSarah
819821
asked Jan 10 at 0:28
SarahSarah
819821
asked Jan 10 at 0:28
SarahSarah
819821
819821
$begingroup$
Well, even for $k=4$ that would seem take a very long time no matter how you try to do it. There would be many such graphs to check, and furthermore, for each such graph many ways to partition the vertices.
$endgroup$
– Mike
Jan 12 at 19:19
add a comment |
$begingroup$
Well, even for $k=4$ that would seem take a very long time no matter how you try to do it. There would be many such graphs to check, and furthermore, for each such graph many ways to partition the vertices.
$endgroup$
– Mike
Jan 12 at 19:19
$begingroup$
Well, even for $k=4$ that would seem take a very long time no matter how you try to do it. There would be many such graphs to check, and furthermore, for each such graph many ways to partition the vertices.
$endgroup$
– Mike
Jan 12 at 19:19
$begingroup$
Well, even for $k=4$ that would seem take a very long time no matter how you try to do it. There would be many such graphs to check, and furthermore, for each such graph many ways to partition the vertices.
$endgroup$
– Mike
Jan 12 at 19:19
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
Yes, you can obtain the numbers by number_of_n_colorings:
sage: from sage.graphs.graph_coloring import number_of_n_colorings
sage: c8 = [number_of_n_colorings(g,5) for g in g8]; c8
[7740,
11640,
...
7140,
6120]
The result is the same as evaluating the chromatic polynomials at $5$:
sage: [g.chromatic_polynomial()(5) for g in g8] == c8
True
You can also obtain all the colorings by using all_graph_colorings:
sage: from sage.graphs.graph_coloring import all_graph_colorings
sage: colorings = [list(all_graph_colorings(g,5)) for g in g8]
The first coloring of the first graph is as follows:
sage: colorings[0][0]
{0: [0, 1, 2, 3, 4], 1: [5, 6], 2: [7]}
The keys in the dictionary are the colors and the values are the lists of vertices with that color (see the vertex_color_dict argument of all_graph_colorings if you want the output the other way around). Hence colorings[0][0].values() is the partition of the vertex set into colors. We can use this partition to plot the graph with colors:
sage: g8[0].plot(partition=colorings[0][0].values())
Also, the list of all colorings agrees with the list of numbers obtained earlier:
sage: [len(c) for c in colorings] == c8
True
answered Jan 15 at 15:54
Ricardo BuringRicardo Buring
1,4711334
$endgroup$
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%2f3068100%2fcommand-to-compute-the-number-of-5-colorings-of-all-2k-k2-graphs%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$
Yes, you can obtain the numbers by number_of_n_colorings:
sage: from sage.graphs.graph_coloring import number_of_n_colorings
sage: c8 = [number_of_n_colorings(g,5) for g in g8]; c8
[7740,
11640,
...
7140,
6120]
The result is the same as evaluating the chromatic polynomials at $5$:
sage: [g.chromatic_polynomial()(5) for g in g8] == c8
True
You can also obtain all the colorings by using all_graph_colorings:
sage: from sage.graphs.graph_coloring import all_graph_colorings
sage: colorings = [list(all_graph_colorings(g,5)) for g in g8]
The first coloring of the first graph is as follows:
sage: colorings[0][0]
{0: [0, 1, 2, 3, 4], 1: [5, 6], 2: [7]}
The keys in the dictionary are the colors and the values are the lists of vertices with that color (see the vertex_color_dict argument of all_graph_colorings if you want the output the other way around). Hence colorings[0][0].values() is the partition of the vertex set into colors. We can use this partition to plot the graph with colors:
sage: g8[0].plot(partition=colorings[0][0].values())
Also, the list of all colorings agrees with the list of numbers obtained earlier:
sage: [len(c) for c in colorings] == c8
True
answered Jan 15 at 15:54
Ricardo BuringRicardo Buring
1,4711334
$endgroup$
add a comment |
$begingroup$
Yes, you can obtain the numbers by number_of_n_colorings:
sage: from sage.graphs.graph_coloring import number_of_n_colorings
sage: c8 = [number_of_n_colorings(g,5) for g in g8]; c8
[7740,
11640,
...
7140,
6120]
The result is the same as evaluating the chromatic polynomials at $5$:
sage: [g.chromatic_polynomial()(5) for g in g8] == c8
True
You can also obtain all the colorings by using all_graph_colorings:
sage: from sage.graphs.graph_coloring import all_graph_colorings
sage: colorings = [list(all_graph_colorings(g,5)) for g in g8]
The first coloring of the first graph is as follows:
sage: colorings[0][0]
{0: [0, 1, 2, 3, 4], 1: [5, 6], 2: [7]}
The keys in the dictionary are the colors and the values are the lists of vertices with that color (see the vertex_color_dict argument of all_graph_colorings if you want the output the other way around). Hence colorings[0][0].values() is the partition of the vertex set into colors. We can use this partition to plot the graph with colors:
sage: g8[0].plot(partition=colorings[0][0].values())
Also, the list of all colorings agrees with the list of numbers obtained earlier:
sage: [len(c) for c in colorings] == c8
True
answered Jan 15 at 15:54
Ricardo BuringRicardo Buring
1,4711334
$endgroup$
add a comment |
$begingroup$
Yes, you can obtain the numbers by number_of_n_colorings:
sage: from sage.graphs.graph_coloring import number_of_n_colorings
sage: c8 = [number_of_n_colorings(g,5) for g in g8]; c8
[7740,
11640,
...
7140,
6120]
The result is the same as evaluating the chromatic polynomials at $5$:
sage: [g.chromatic_polynomial()(5) for g in g8] == c8
True
You can also obtain all the colorings by using all_graph_colorings:
sage: from sage.graphs.graph_coloring import all_graph_colorings
sage: colorings = [list(all_graph_colorings(g,5)) for g in g8]
The first coloring of the first graph is as follows:
sage: colorings[0][0]
{0: [0, 1, 2, 3, 4], 1: [5, 6], 2: [7]}
The keys in the dictionary are the colors and the values are the lists of vertices with that color (see the vertex_color_dict argument of all_graph_colorings if you want the output the other way around). Hence colorings[0][0].values() is the partition of the vertex set into colors. We can use this partition to plot the graph with colors:
sage: g8[0].plot(partition=colorings[0][0].values())
Also, the list of all colorings agrees with the list of numbers obtained earlier:
sage: [len(c) for c in colorings] == c8
True
answered Jan 15 at 15:54
Ricardo BuringRicardo Buring
1,4711334
$endgroup$
Yes, you can obtain the numbers by number_of_n_colorings:
sage: from sage.graphs.graph_coloring import number_of_n_colorings
sage: c8 = [number_of_n_colorings(g,5) for g in g8]; c8
[7740,
11640,
...
7140,
6120]
The result is the same as evaluating the chromatic polynomials at $5$:
sage: [g.chromatic_polynomial()(5) for g in g8] == c8
True
You can also obtain all the colorings by using all_graph_colorings:
sage: from sage.graphs.graph_coloring import all_graph_colorings
sage: colorings = [list(all_graph_colorings(g,5)) for g in g8]
The first coloring of the first graph is as follows:
sage: colorings[0][0]
{0: [0, 1, 2, 3, 4], 1: [5, 6], 2: [7]}
The keys in the dictionary are the colors and the values are the lists of vertices with that color (see the vertex_color_dict argument of all_graph_colorings if you want the output the other way around). Hence colorings[0][0].values() is the partition of the vertex set into colors. We can use this partition to plot the graph with colors:
sage: g8[0].plot(partition=colorings[0][0].values())
Also, the list of all colorings agrees with the list of numbers obtained earlier:
sage: [len(c) for c in colorings] == c8
True
answered Jan 15 at 15:54
Ricardo BuringRicardo Buring
1,4711334
edited Jan 15 at 16:01
answered Jan 15 at 15:54
Ricardo BuringRicardo Buring
1,4711334
answered Jan 15 at 15:54
Ricardo BuringRicardo Buring
1,4711334
answered Jan 15 at 15:54
Ricardo BuringRicardo Buring
1,4711334
1,4711334
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.
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%2f3068100%2fcommand-to-compute-the-number-of-5-colorings-of-all-2k-k2-graphs%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$
Well, even for $k=4$ that would seem take a very long time no matter how you try to do it. There would be many such graphs to check, and furthermore, for each such graph many ways to partition the vertices.
$endgroup$
– Mike
Jan 12 at 19:19