Mixing
Greedy algorithm fails to give chromatic number
$begingroup$
Produce a graph and degree sequence for which the greedy algorithm fails to give the chromatic number.
My first example is below- The first labeling uses 2 colors which is the chromatic number and the second labeling uses 3 colors, which shows that the greedy algorithm fails to give the chromatic number. The degree sequence of this graph is {3,3,2,2,1,1}.
I need to find a second example of this situation. Is there a systematic way to find another example? Is there a pattern in the degree sequence of graphs when the greedy alg. will fail to give the chromatic number? Or to find a second example will I just need to try random graphs and labelings?
*I also know that different labelings will produce different colorings when using the greedy algorithm.
graph-theory examples-counterexamples coloring
asked Feb 13 '16 at 19:26
user2553807user2553807
615830
$endgroup$
add a comment |
$begingroup$
Produce a graph and degree sequence for which the greedy algorithm fails to give the chromatic number.
My first example is below- The first labeling uses 2 colors which is the chromatic number and the second labeling uses 3 colors, which shows that the greedy algorithm fails to give the chromatic number. The degree sequence of this graph is {3,3,2,2,1,1}.
I need to find a second example of this situation. Is there a systematic way to find another example? Is there a pattern in the degree sequence of graphs when the greedy alg. will fail to give the chromatic number? Or to find a second example will I just need to try random graphs and labelings?
*I also know that different labelings will produce different colorings when using the greedy algorithm.
graph-theory examples-counterexamples coloring
asked Feb 13 '16 at 19:26
user2553807user2553807
615830
$endgroup$
1
$begingroup$
The greedy algorithm will fail in a bipartite graph, if it picks the vertices in the wrong order...
$endgroup$
– Michael Biro
Feb 13 '16 at 19:48
add a comment |
$begingroup$
Produce a graph and degree sequence for which the greedy algorithm fails to give the chromatic number.
My first example is below- The first labeling uses 2 colors which is the chromatic number and the second labeling uses 3 colors, which shows that the greedy algorithm fails to give the chromatic number. The degree sequence of this graph is {3,3,2,2,1,1}.
I need to find a second example of this situation. Is there a systematic way to find another example? Is there a pattern in the degree sequence of graphs when the greedy alg. will fail to give the chromatic number? Or to find a second example will I just need to try random graphs and labelings?
*I also know that different labelings will produce different colorings when using the greedy algorithm.
graph-theory examples-counterexamples coloring
asked Feb 13 '16 at 19:26
user2553807user2553807
615830
$endgroup$
Produce a graph and degree sequence for which the greedy algorithm fails to give the chromatic number.
My first example is below- The first labeling uses 2 colors which is the chromatic number and the second labeling uses 3 colors, which shows that the greedy algorithm fails to give the chromatic number. The degree sequence of this graph is {3,3,2,2,1,1}.
I need to find a second example of this situation. Is there a systematic way to find another example? Is there a pattern in the degree sequence of graphs when the greedy alg. will fail to give the chromatic number? Or to find a second example will I just need to try random graphs and labelings?
*I also know that different labelings will produce different colorings when using the greedy algorithm.
graph-theory examples-counterexamples coloring
graph-theory examples-counterexamples coloring
asked Feb 13 '16 at 19:26
user2553807user2553807
615830
asked Feb 13 '16 at 19:26
user2553807user2553807
615830
edited Feb 13 '16 at 19:33
user2553807
asked Feb 13 '16 at 19:26
user2553807user2553807
615830
asked Feb 13 '16 at 19:26
user2553807user2553807
615830
asked Feb 13 '16 at 19:26
user2553807user2553807
615830
615830
1
$begingroup$
The greedy algorithm will fail in a bipartite graph, if it picks the vertices in the wrong order...
$endgroup$
– Michael Biro
Feb 13 '16 at 19:48
add a comment |
1
$begingroup$
The greedy algorithm will fail in a bipartite graph, if it picks the vertices in the wrong order...
$endgroup$
– Michael Biro
Feb 13 '16 at 19:48
1
1
$begingroup$
The greedy algorithm will fail in a bipartite graph, if it picks the vertices in the wrong order...
$endgroup$
– Michael Biro
Feb 13 '16 at 19:48
$begingroup$
The greedy algorithm will fail in a bipartite graph, if it picks the vertices in the wrong order...
$endgroup$
– Michael Biro
Feb 13 '16 at 19:48
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
There are a lot of ways to do that, here is the first one i thought of. Suppose you have a graph $G$ with chromatic number at least two and different vertices $x$ and $y$ that always get the same color in every $chi(G)$-coloring of $G$. Add a new vertex $z$ and the edge $zx$ to get a graph $G'$. Then $chi(G') = chi(G)$. Now label $G'$ so that the ordering starts with $z, y, x$. The greedy algorithm will give $z$ color 0, $y$ color 0 and $x$ color 1. Since $x$ and $y$ got different colors, our assumption implies that any way to finish the coloring will use at least $chi(G') + 1$ colors, in particular the greedy algorithm will.
Lots of ways to get such a $G$ with $x$ and $y$, one is take a complete graph and remove one edge.
answered Mar 25 '18 at 12:49
landon rabernlandon rabern
1
$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%2f1653574%2fgreedy-algorithm-fails-to-give-chromatic-number%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$
There are a lot of ways to do that, here is the first one i thought of. Suppose you have a graph $G$ with chromatic number at least two and different vertices $x$ and $y$ that always get the same color in every $chi(G)$-coloring of $G$. Add a new vertex $z$ and the edge $zx$ to get a graph $G'$. Then $chi(G') = chi(G)$. Now label $G'$ so that the ordering starts with $z, y, x$. The greedy algorithm will give $z$ color 0, $y$ color 0 and $x$ color 1. Since $x$ and $y$ got different colors, our assumption implies that any way to finish the coloring will use at least $chi(G') + 1$ colors, in particular the greedy algorithm will.
Lots of ways to get such a $G$ with $x$ and $y$, one is take a complete graph and remove one edge.
answered Mar 25 '18 at 12:49
landon rabernlandon rabern
1
$endgroup$
add a comment |
$begingroup$
There are a lot of ways to do that, here is the first one i thought of. Suppose you have a graph $G$ with chromatic number at least two and different vertices $x$ and $y$ that always get the same color in every $chi(G)$-coloring of $G$. Add a new vertex $z$ and the edge $zx$ to get a graph $G'$. Then $chi(G') = chi(G)$. Now label $G'$ so that the ordering starts with $z, y, x$. The greedy algorithm will give $z$ color 0, $y$ color 0 and $x$ color 1. Since $x$ and $y$ got different colors, our assumption implies that any way to finish the coloring will use at least $chi(G') + 1$ colors, in particular the greedy algorithm will.
Lots of ways to get such a $G$ with $x$ and $y$, one is take a complete graph and remove one edge.
answered Mar 25 '18 at 12:49
landon rabernlandon rabern
1
$endgroup$
add a comment |
$begingroup$
There are a lot of ways to do that, here is the first one i thought of. Suppose you have a graph $G$ with chromatic number at least two and different vertices $x$ and $y$ that always get the same color in every $chi(G)$-coloring of $G$. Add a new vertex $z$ and the edge $zx$ to get a graph $G'$. Then $chi(G') = chi(G)$. Now label $G'$ so that the ordering starts with $z, y, x$. The greedy algorithm will give $z$ color 0, $y$ color 0 and $x$ color 1. Since $x$ and $y$ got different colors, our assumption implies that any way to finish the coloring will use at least $chi(G') + 1$ colors, in particular the greedy algorithm will.
Lots of ways to get such a $G$ with $x$ and $y$, one is take a complete graph and remove one edge.
answered Mar 25 '18 at 12:49
landon rabernlandon rabern
1
$endgroup$
There are a lot of ways to do that, here is the first one i thought of. Suppose you have a graph $G$ with chromatic number at least two and different vertices $x$ and $y$ that always get the same color in every $chi(G)$-coloring of $G$. Add a new vertex $z$ and the edge $zx$ to get a graph $G'$. Then $chi(G') = chi(G)$. Now label $G'$ so that the ordering starts with $z, y, x$. The greedy algorithm will give $z$ color 0, $y$ color 0 and $x$ color 1. Since $x$ and $y$ got different colors, our assumption implies that any way to finish the coloring will use at least $chi(G') + 1$ colors, in particular the greedy algorithm will.
Lots of ways to get such a $G$ with $x$ and $y$, one is take a complete graph and remove one edge.
answered Mar 25 '18 at 12:49
landon rabernlandon rabern
1
answered Mar 25 '18 at 12:49
landon rabernlandon rabern
1
answered Mar 25 '18 at 12:49
landon rabernlandon rabern
1
answered Mar 25 '18 at 12:49
landon rabernlandon rabern
1
1
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%2f1653574%2fgreedy-algorithm-fails-to-give-chromatic-number%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
1
$begingroup$
The greedy algorithm will fail in a bipartite graph, if it picks the vertices in the wrong order...
$endgroup$
– Michael Biro
Feb 13 '16 at 19:48