Vertex order for Greed coloring of a Graph The Next CEO of Stack OverflowSequential algorithm for coloring graphs- there exists an ordering of vertices where it finds a coloring with $chi(G)$ colors.Coloring graph with 3 colorsWhy is Welsh-Powell algorithm better than the basic greedy algorithm for graph coloring?An algorithm for proper edge-coloring of every simple graph with $delta+1$ colorsHow I can find planar graph for which greedy vertex coloring find coloring with 7 colors?Optimally coloring the vertices of a graph subject to constraintsPolynomial vertex coloring algorithmShowing a coloring for a graphGraph vertex-coloringvertex coloring of a graph $G$ such that colors appear twice
Is it possible to make a 9x9 table fit within the default margins?
How to show a landlord what we have in savings?
What did the word "leisure" mean in late 18th Century usage?
Another proof that dividing by 0 does not exist -- is it right?
How to pronounce fünf in 45
How can I separate the number from the unit in argument?
Shortening a title without changing its meaning
Incomplete cube
Would a grinding machine be a simple and workable propulsion system for an interplanetary spacecraft?
Arrows in tikz Markov chain diagram overlap
How dangerous is XSS
That's an odd coin - I wonder why
What is the difference between 'contrib' and 'non-free' packages repositories?
How to coordinate airplane tickets?
Gauss' Posthumous Publications?
Does the Idaho Potato Commission associate potato skins with healthy eating?
Can a PhD from a non-TU9 German university become a professor in a TU9 university?
Cannot restore registry to default in Windows 10?
My boss doesn't want me to have a side project
Could a dragon use its wings to swim?
Finitely generated matrix groups whose eigenvalues are all algebraic
Compensation for working overtime on Saturdays
How can I prove that a state of equilibrium is unstable?
Masking layers by a vector polygon layer in QGIS
Vertex order for Greed coloring of a Graph
The Next CEO of Stack OverflowSequential algorithm for coloring graphs- there exists an ordering of vertices where it finds a coloring with $chi(G)$ colors.Coloring graph with 3 colorsWhy is Welsh-Powell algorithm better than the basic greedy algorithm for graph coloring?An algorithm for proper edge-coloring of every simple graph with $delta+1$ colorsHow I can find planar graph for which greedy vertex coloring find coloring with 7 colors?Optimally coloring the vertices of a graph subject to constraintsPolynomial vertex coloring algorithmShowing a coloring for a graphGraph vertex-coloringvertex coloring of a graph $G$ such that colors appear twice
$begingroup$
I'm interested in coloring the graph $G$ with the greedy algorithm. Now I know that the result can depend on the vertex order and can also be very bad. Now I want to show that there is a vertex order for which the Greedy algorithm gives an optimal result. Intuitive I understand that if there is a perfect coloration for $G$ then you take it and arrange the vertex in ascending colors. But how can I formally prove that the coloration provided by the greedy algorithm with this vertex order is really less than or equal to the given coloration ?
graph-theory coloring
asked Mar 20 at 10:14
iogeoaiogeoa
111
$endgroup$
add a comment |
$begingroup$
I'm interested in coloring the graph $G$ with the greedy algorithm. Now I know that the result can depend on the vertex order and can also be very bad. Now I want to show that there is a vertex order for which the Greedy algorithm gives an optimal result. Intuitive I understand that if there is a perfect coloration for $G$ then you take it and arrange the vertex in ascending colors. But how can I formally prove that the coloration provided by the greedy algorithm with this vertex order is really less than or equal to the given coloration ?
graph-theory coloring
asked Mar 20 at 10:14
iogeoaiogeoa
111
$endgroup$
add a comment |
$begingroup$
I'm interested in coloring the graph $G$ with the greedy algorithm. Now I know that the result can depend on the vertex order and can also be very bad. Now I want to show that there is a vertex order for which the Greedy algorithm gives an optimal result. Intuitive I understand that if there is a perfect coloration for $G$ then you take it and arrange the vertex in ascending colors. But how can I formally prove that the coloration provided by the greedy algorithm with this vertex order is really less than or equal to the given coloration ?
graph-theory coloring
asked Mar 20 at 10:14
iogeoaiogeoa
111
$endgroup$
I'm interested in coloring the graph $G$ with the greedy algorithm. Now I know that the result can depend on the vertex order and can also be very bad. Now I want to show that there is a vertex order for which the Greedy algorithm gives an optimal result. Intuitive I understand that if there is a perfect coloration for $G$ then you take it and arrange the vertex in ascending colors. But how can I formally prove that the coloration provided by the greedy algorithm with this vertex order is really less than or equal to the given coloration ?
graph-theory coloring
graph-theory coloring
asked Mar 20 at 10:14
iogeoaiogeoa
111
asked Mar 20 at 10:14
iogeoaiogeoa
111
asked Mar 20 at 10:14
iogeoaiogeoa
111
asked Mar 20 at 10:14
iogeoaiogeoa
111
asked Mar 20 at 10:14
iogeoaiogeoa
111
111
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
Just check what happens during execution of the algorithm.
You have colors $c_1,ldots,c_k$ and you list the vertices according to their color classes $X_1,ldots,X_k$, i.e. all vertices of $X_i$ have color $c_i$. The order of the vertices within one color class does not matter. Now the color classes form independent sets, so as long as you are coloring vertices of $X_1$, you will always use color $c_1$.
If you start coloring vertices of $X_2$, you may still be able to use color $c_1$(!), but you will certainly always be able to use color $c_2$, since all previously colored vertices either have color $c_1$, or they are in $X_2$, which is an independent set.
The general idea is that you never need to use color $c_i$ before you are coloring vertices of $X_i$.
I trust you can extend this idea to a proper proof using induction.
answered Mar 20 at 11:13
Leen DroogendijkLeen Droogendijk
6,1651716
$endgroup$
add a comment |
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%2f3155238%2fvertex-order-for-greed-coloring-of-a-graph%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$
Just check what happens during execution of the algorithm.
You have colors $c_1,ldots,c_k$ and you list the vertices according to their color classes $X_1,ldots,X_k$, i.e. all vertices of $X_i$ have color $c_i$. The order of the vertices within one color class does not matter. Now the color classes form independent sets, so as long as you are coloring vertices of $X_1$, you will always use color $c_1$.
If you start coloring vertices of $X_2$, you may still be able to use color $c_1$(!), but you will certainly always be able to use color $c_2$, since all previously colored vertices either have color $c_1$, or they are in $X_2$, which is an independent set.
The general idea is that you never need to use color $c_i$ before you are coloring vertices of $X_i$.
I trust you can extend this idea to a proper proof using induction.
answered Mar 20 at 11:13
Leen DroogendijkLeen Droogendijk
6,1651716
$endgroup$
add a comment |
$begingroup$
Just check what happens during execution of the algorithm.
You have colors $c_1,ldots,c_k$ and you list the vertices according to their color classes $X_1,ldots,X_k$, i.e. all vertices of $X_i$ have color $c_i$. The order of the vertices within one color class does not matter. Now the color classes form independent sets, so as long as you are coloring vertices of $X_1$, you will always use color $c_1$.
If you start coloring vertices of $X_2$, you may still be able to use color $c_1$(!), but you will certainly always be able to use color $c_2$, since all previously colored vertices either have color $c_1$, or they are in $X_2$, which is an independent set.
The general idea is that you never need to use color $c_i$ before you are coloring vertices of $X_i$.
I trust you can extend this idea to a proper proof using induction.
answered Mar 20 at 11:13
Leen DroogendijkLeen Droogendijk
6,1651716
$endgroup$
add a comment |
$begingroup$
Just check what happens during execution of the algorithm.
You have colors $c_1,ldots,c_k$ and you list the vertices according to their color classes $X_1,ldots,X_k$, i.e. all vertices of $X_i$ have color $c_i$. The order of the vertices within one color class does not matter. Now the color classes form independent sets, so as long as you are coloring vertices of $X_1$, you will always use color $c_1$.
If you start coloring vertices of $X_2$, you may still be able to use color $c_1$(!), but you will certainly always be able to use color $c_2$, since all previously colored vertices either have color $c_1$, or they are in $X_2$, which is an independent set.
The general idea is that you never need to use color $c_i$ before you are coloring vertices of $X_i$.
I trust you can extend this idea to a proper proof using induction.
answered Mar 20 at 11:13
Leen DroogendijkLeen Droogendijk
6,1651716
$endgroup$
Just check what happens during execution of the algorithm.
You have colors $c_1,ldots,c_k$ and you list the vertices according to their color classes $X_1,ldots,X_k$, i.e. all vertices of $X_i$ have color $c_i$. The order of the vertices within one color class does not matter. Now the color classes form independent sets, so as long as you are coloring vertices of $X_1$, you will always use color $c_1$.
If you start coloring vertices of $X_2$, you may still be able to use color $c_1$(!), but you will certainly always be able to use color $c_2$, since all previously colored vertices either have color $c_1$, or they are in $X_2$, which is an independent set.
The general idea is that you never need to use color $c_i$ before you are coloring vertices of $X_i$.
I trust you can extend this idea to a proper proof using induction.
answered Mar 20 at 11:13
Leen DroogendijkLeen Droogendijk
6,1651716
answered Mar 20 at 11:13
Leen DroogendijkLeen Droogendijk
6,1651716
answered Mar 20 at 11:13
Leen DroogendijkLeen Droogendijk
6,1651716
answered Mar 20 at 11:13
Leen DroogendijkLeen Droogendijk
6,1651716
6,1651716
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%2f3155238%2fvertex-order-for-greed-coloring-of-a-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
