Petersen graph edge chromatic number
Hi I keep on getting 3 for the edge chromatic number of the Petersen graph. But the Petersen graph has edge chromatic number of 4 and I don’t know how to do that. Can someone please show this by proving this.
discrete-mathematics graph-theory problem-solving coloring
edited Nov 30 '18 at 3:25
bof
50.5k457119
asked Nov 30 '18 at 1:33
Tom Tom
41
add a comment |
Hi I keep on getting 3 for the edge chromatic number of the Petersen graph. But the Petersen graph has edge chromatic number of 4 and I don’t know how to do that. Can someone please show this by proving this.
discrete-mathematics graph-theory problem-solving coloring
edited Nov 30 '18 at 3:25
bof
50.5k457119
asked Nov 30 '18 at 1:33
Tom Tom
41
3
What do you mean, you "got $3$" for the edge chromatic number? Does that mean you found a proper edge coloring with $3$ colors? If you did that, then you proved that the edge chromatic number is no greater than $3$. How else would you "get $3$"?
– bof
Nov 30 '18 at 3:27
add a comment |
Hi I keep on getting 3 for the edge chromatic number of the Petersen graph. But the Petersen graph has edge chromatic number of 4 and I don’t know how to do that. Can someone please show this by proving this.
discrete-mathematics graph-theory problem-solving coloring
edited Nov 30 '18 at 3:25
bof
50.5k457119
asked Nov 30 '18 at 1:33
Tom Tom
41
Hi I keep on getting 3 for the edge chromatic number of the Petersen graph. But the Petersen graph has edge chromatic number of 4 and I don’t know how to do that. Can someone please show this by proving this.
discrete-mathematics graph-theory problem-solving coloring
discrete-mathematics graph-theory problem-solving coloring
edited Nov 30 '18 at 3:25
bof
50.5k457119
asked Nov 30 '18 at 1:33
Tom Tom
41
edited Nov 30 '18 at 3:25
bof
50.5k457119
asked Nov 30 '18 at 1:33
Tom Tom
41
edited Nov 30 '18 at 3:25
bof
50.5k457119
edited Nov 30 '18 at 3:25
bof
50.5k457119
edited Nov 30 '18 at 3:25
bof
50.5k457119
50.5k457119
asked Nov 30 '18 at 1:33
Tom Tom
41
asked Nov 30 '18 at 1:33
Tom Tom
41
asked Nov 30 '18 at 1:33
Tom Tom
41
41
3
What do you mean, you "got $3$" for the edge chromatic number? Does that mean you found a proper edge coloring with $3$ colors? If you did that, then you proved that the edge chromatic number is no greater than $3$. How else would you "get $3$"?
– bof
Nov 30 '18 at 3:27
add a comment |
3
What do you mean, you "got $3$" for the edge chromatic number? Does that mean you found a proper edge coloring with $3$ colors? If you did that, then you proved that the edge chromatic number is no greater than $3$. How else would you "get $3$"?
– bof
Nov 30 '18 at 3:27
3
3
What do you mean, you "got $3$" for the edge chromatic number? Does that mean you found a proper edge coloring with $3$ colors? If you did that, then you proved that the edge chromatic number is no greater than $3$. How else would you "get $3$"?
– bof
Nov 30 '18 at 3:27
What do you mean, you "got $3$" for the edge chromatic number? Does that mean you found a proper edge coloring with $3$ colors? If you did that, then you proved that the edge chromatic number is no greater than $3$. How else would you "get $3$"?
– bof
Nov 30 '18 at 3:27
add a comment |
1 Answer
1
active
oldest
votes
Every cubic bridgeless graph has a perfect matching, hence we can find a perfect matching for the peterson graph and color the matched edges in one color. You can check that n o matter which perfect matching you choose to remove, After you remove the matched edges, you get two disjoint cycles on 5 vertices each. We know an odd cycle needs 3 colors to properly color the edges. Hence we can color the peterson graph using at most 4 colors and not less. So it's edge chromatic number is 4. I hope I did it right.
answered Nov 30 '18 at 22:47
mathnoobmathnoob
1,797422
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%2f3019499%2fpetersen-graph-edge-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
Every cubic bridgeless graph has a perfect matching, hence we can find a perfect matching for the peterson graph and color the matched edges in one color. You can check that n o matter which perfect matching you choose to remove, After you remove the matched edges, you get two disjoint cycles on 5 vertices each. We know an odd cycle needs 3 colors to properly color the edges. Hence we can color the peterson graph using at most 4 colors and not less. So it's edge chromatic number is 4. I hope I did it right.
answered Nov 30 '18 at 22:47
mathnoobmathnoob
1,797422
add a comment |
Every cubic bridgeless graph has a perfect matching, hence we can find a perfect matching for the peterson graph and color the matched edges in one color. You can check that n o matter which perfect matching you choose to remove, After you remove the matched edges, you get two disjoint cycles on 5 vertices each. We know an odd cycle needs 3 colors to properly color the edges. Hence we can color the peterson graph using at most 4 colors and not less. So it's edge chromatic number is 4. I hope I did it right.
answered Nov 30 '18 at 22:47
mathnoobmathnoob
1,797422
add a comment |
Every cubic bridgeless graph has a perfect matching, hence we can find a perfect matching for the peterson graph and color the matched edges in one color. You can check that n o matter which perfect matching you choose to remove, After you remove the matched edges, you get two disjoint cycles on 5 vertices each. We know an odd cycle needs 3 colors to properly color the edges. Hence we can color the peterson graph using at most 4 colors and not less. So it's edge chromatic number is 4. I hope I did it right.
answered Nov 30 '18 at 22:47
mathnoobmathnoob
1,797422
Every cubic bridgeless graph has a perfect matching, hence we can find a perfect matching for the peterson graph and color the matched edges in one color. You can check that n o matter which perfect matching you choose to remove, After you remove the matched edges, you get two disjoint cycles on 5 vertices each. We know an odd cycle needs 3 colors to properly color the edges. Hence we can color the peterson graph using at most 4 colors and not less. So it's edge chromatic number is 4. I hope I did it right.
answered Nov 30 '18 at 22:47
mathnoobmathnoob
1,797422
answered Nov 30 '18 at 22:47
mathnoobmathnoob
1,797422
answered Nov 30 '18 at 22:47
mathnoobmathnoob
1,797422
answered Nov 30 '18 at 22:47
mathnoobmathnoob
1,797422
1,797422
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%2f3019499%2fpetersen-graph-edge-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
3
What do you mean, you "got $3$" for the edge chromatic number? Does that mean you found a proper edge coloring with $3$ colors? If you did that, then you proved that the edge chromatic number is no greater than $3$. How else would you "get $3$"?
– bof
Nov 30 '18 at 3:27