Mixing
3-edge colorable cubic graph with an embedding on an orientable surface that is not 4-face colorable
$begingroup$
Let $G$ be a simple cubic graph that is cellularly embedded on a surface such that the regions of $G$ are 4-colorable. Then by labeling the colors by the elements of $mathbb{Z}/2mathbb{Z} times mathbb{Z}/2mathbb{Z}$, we can 3-color the edges by taking the color of each edge to be the sum of its two adjacent regions.
The converse of this works for planar graphs - namely a 3-edge coloring can be converted into a face coloring. I would like to know an example where this fails for higher genus cubic graphs. Namely, is there an example of a cubic 3-edge colorable graph cellularly embedded of a surface that is not 4-region colorable?
graph-theory coloring topological-graph-theory
asked Jan 21 at 1:24
user101010user101010
1,953416
$endgroup$
add a comment |
$begingroup$
Let $G$ be a simple cubic graph that is cellularly embedded on a surface such that the regions of $G$ are 4-colorable. Then by labeling the colors by the elements of $mathbb{Z}/2mathbb{Z} times mathbb{Z}/2mathbb{Z}$, we can 3-color the edges by taking the color of each edge to be the sum of its two adjacent regions.
The converse of this works for planar graphs - namely a 3-edge coloring can be converted into a face coloring. I would like to know an example where this fails for higher genus cubic graphs. Namely, is there an example of a cubic 3-edge colorable graph cellularly embedded of a surface that is not 4-region colorable?
graph-theory coloring topological-graph-theory
asked Jan 21 at 1:24
user101010user101010
1,953416
$endgroup$
$begingroup$
I think that for your first process to be correct, you also need the Graph $G$ to be bridgeless. This is the key point as you will never have an edge colored by (0,0) is $G$ is bridgeless, hence reducing to 3 colors. Otherwise this does not work.
$endgroup$
– Thomas Lesgourgues
Jan 21 at 11:45
$begingroup$
@ThomasLesgourgues You're right - without reading too carefully, I assumed that this was one of the things implied by "cellular embedding" (when there's a bridge, the face that's on both sides of that bridge is kind of awkward) but it's not (apparently it's not awkward enough, according to Wikipedia.) Although maybe we might not consider a graph where a face borders itself to be $4$-colorable, or colorable at all.
$endgroup$
– Misha Lavrov
Jan 21 at 17:44
$begingroup$
@ThomasLesgourgues The condition that the regions of the graph on the surface are 4-colorable implies that we don't have anything like that going on.
$endgroup$
– user101010
Jan 22 at 1:19
$begingroup$
@user101010. I think this is wrong, ANY planar graph is 4 face colorable, this is actually just the 4 color theorem. But you need the graph to be bridgeless in order to transfer the 4-face coloring into a 3-edge coloring. I might be wrong, happy to discuss
$endgroup$
– Thomas Lesgourgues
Jan 22 at 9:30
add a comment |
$begingroup$
Let $G$ be a simple cubic graph that is cellularly embedded on a surface such that the regions of $G$ are 4-colorable. Then by labeling the colors by the elements of $mathbb{Z}/2mathbb{Z} times mathbb{Z}/2mathbb{Z}$, we can 3-color the edges by taking the color of each edge to be the sum of its two adjacent regions.
The converse of this works for planar graphs - namely a 3-edge coloring can be converted into a face coloring. I would like to know an example where this fails for higher genus cubic graphs. Namely, is there an example of a cubic 3-edge colorable graph cellularly embedded of a surface that is not 4-region colorable?
graph-theory coloring topological-graph-theory
asked Jan 21 at 1:24
user101010user101010
1,953416
$endgroup$
Let $G$ be a simple cubic graph that is cellularly embedded on a surface such that the regions of $G$ are 4-colorable. Then by labeling the colors by the elements of $mathbb{Z}/2mathbb{Z} times mathbb{Z}/2mathbb{Z}$, we can 3-color the edges by taking the color of each edge to be the sum of its two adjacent regions.
The converse of this works for planar graphs - namely a 3-edge coloring can be converted into a face coloring. I would like to know an example where this fails for higher genus cubic graphs. Namely, is there an example of a cubic 3-edge colorable graph cellularly embedded of a surface that is not 4-region colorable?
graph-theory coloring topological-graph-theory
graph-theory coloring topological-graph-theory
asked Jan 21 at 1:24
user101010user101010
1,953416
asked Jan 21 at 1:24
user101010user101010
1,953416
asked Jan 21 at 1:24
user101010user101010
1,953416
asked Jan 21 at 1:24
user101010user101010
1,953416
asked Jan 21 at 1:24
user101010user101010
1,953416
1,953416
$begingroup$
I think that for your first process to be correct, you also need the Graph $G$ to be bridgeless. This is the key point as you will never have an edge colored by (0,0) is $G$ is bridgeless, hence reducing to 3 colors. Otherwise this does not work.
$endgroup$
– Thomas Lesgourgues
Jan 21 at 11:45
$begingroup$
@ThomasLesgourgues You're right - without reading too carefully, I assumed that this was one of the things implied by "cellular embedding" (when there's a bridge, the face that's on both sides of that bridge is kind of awkward) but it's not (apparently it's not awkward enough, according to Wikipedia.) Although maybe we might not consider a graph where a face borders itself to be $4$-colorable, or colorable at all.
$endgroup$
– Misha Lavrov
Jan 21 at 17:44
$begingroup$
@ThomasLesgourgues The condition that the regions of the graph on the surface are 4-colorable implies that we don't have anything like that going on.
$endgroup$
– user101010
Jan 22 at 1:19
$begingroup$
@user101010. I think this is wrong, ANY planar graph is 4 face colorable, this is actually just the 4 color theorem. But you need the graph to be bridgeless in order to transfer the 4-face coloring into a 3-edge coloring. I might be wrong, happy to discuss
$endgroup$
– Thomas Lesgourgues
Jan 22 at 9:30
add a comment |
$begingroup$
I think that for your first process to be correct, you also need the Graph $G$ to be bridgeless. This is the key point as you will never have an edge colored by (0,0) is $G$ is bridgeless, hence reducing to 3 colors. Otherwise this does not work.
$endgroup$
– Thomas Lesgourgues
Jan 21 at 11:45
$begingroup$
@ThomasLesgourgues You're right - without reading too carefully, I assumed that this was one of the things implied by "cellular embedding" (when there's a bridge, the face that's on both sides of that bridge is kind of awkward) but it's not (apparently it's not awkward enough, according to Wikipedia.) Although maybe we might not consider a graph where a face borders itself to be $4$-colorable, or colorable at all.
$endgroup$
– Misha Lavrov
Jan 21 at 17:44
$begingroup$
@ThomasLesgourgues The condition that the regions of the graph on the surface are 4-colorable implies that we don't have anything like that going on.
$endgroup$
– user101010
Jan 22 at 1:19
$begingroup$
@user101010. I think this is wrong, ANY planar graph is 4 face colorable, this is actually just the 4 color theorem. But you need the graph to be bridgeless in order to transfer the 4-face coloring into a 3-edge coloring. I might be wrong, happy to discuss
$endgroup$
– Thomas Lesgourgues
Jan 22 at 9:30
$begingroup$
I think that for your first process to be correct, you also need the Graph $G$ to be bridgeless. This is the key point as you will never have an edge colored by (0,0) is $G$ is bridgeless, hence reducing to 3 colors. Otherwise this does not work.
$endgroup$
– Thomas Lesgourgues
Jan 21 at 11:45
$begingroup$
I think that for your first process to be correct, you also need the Graph $G$ to be bridgeless. This is the key point as you will never have an edge colored by (0,0) is $G$ is bridgeless, hence reducing to 3 colors. Otherwise this does not work.
$endgroup$
– Thomas Lesgourgues
Jan 21 at 11:45
$begingroup$
@ThomasLesgourgues You're right - without reading too carefully, I assumed that this was one of the things implied by "cellular embedding" (when there's a bridge, the face that's on both sides of that bridge is kind of awkward) but it's not (apparently it's not awkward enough, according to Wikipedia.) Although maybe we might not consider a graph where a face borders itself to be $4$-colorable, or colorable at all.
$endgroup$
– Misha Lavrov
Jan 21 at 17:44
$begingroup$
@ThomasLesgourgues You're right - without reading too carefully, I assumed that this was one of the things implied by "cellular embedding" (when there's a bridge, the face that's on both sides of that bridge is kind of awkward) but it's not (apparently it's not awkward enough, according to Wikipedia.) Although maybe we might not consider a graph where a face borders itself to be $4$-colorable, or colorable at all.
$endgroup$
– Misha Lavrov
Jan 21 at 17:44
$begingroup$
@ThomasLesgourgues The condition that the regions of the graph on the surface are 4-colorable implies that we don't have anything like that going on.
$endgroup$
– user101010
Jan 22 at 1:19
$begingroup$
@ThomasLesgourgues The condition that the regions of the graph on the surface are 4-colorable implies that we don't have anything like that going on.
$endgroup$
– user101010
Jan 22 at 1:19
$begingroup$
@user101010. I think this is wrong, ANY planar graph is 4 face colorable, this is actually just the 4 color theorem. But you need the graph to be bridgeless in order to transfer the 4-face coloring into a 3-edge coloring. I might be wrong, happy to discuss
$endgroup$
– Thomas Lesgourgues
Jan 22 at 9:30
$begingroup$
@user101010. I think this is wrong, ANY planar graph is 4 face colorable, this is actually just the 4 color theorem. But you need the graph to be bridgeless in order to transfer the 4-face coloring into a 3-edge coloring. I might be wrong, happy to discuss
$endgroup$
– Thomas Lesgourgues
Jan 22 at 9:30
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
Take a cellular embedding of $K_5$ in the torus, and turn it into a cubic graph by replacing each vertex by a $4$-cycle. Here's what this might look like:
The result is $3$-edge-colorable: color the edges of each $4$-cycle using two of the colors, and use the third color on the long edges.
However, the faces of this embedding are not $4$-colorable. You can check that any two of the large faces of length $8$ are adjacent to each other (and therefore coloring all $5$ of these faces takes $5$ distinct colors).
answered Jan 21 at 3:49
Misha LavrovMisha Lavrov
47.2k657107
$endgroup$
$begingroup$
Thank you - this is perfect!
$endgroup$
– user101010
Jan 21 at 5:58
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%2f3081373%2f3-edge-colorable-cubic-graph-with-an-embedding-on-an-orientable-surface-that-is%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$
Take a cellular embedding of $K_5$ in the torus, and turn it into a cubic graph by replacing each vertex by a $4$-cycle. Here's what this might look like:
The result is $3$-edge-colorable: color the edges of each $4$-cycle using two of the colors, and use the third color on the long edges.
However, the faces of this embedding are not $4$-colorable. You can check that any two of the large faces of length $8$ are adjacent to each other (and therefore coloring all $5$ of these faces takes $5$ distinct colors).
answered Jan 21 at 3:49
Misha LavrovMisha Lavrov
47.2k657107
$endgroup$
$begingroup$
Thank you - this is perfect!
$endgroup$
– user101010
Jan 21 at 5:58
add a comment |
$begingroup$
Take a cellular embedding of $K_5$ in the torus, and turn it into a cubic graph by replacing each vertex by a $4$-cycle. Here's what this might look like:
The result is $3$-edge-colorable: color the edges of each $4$-cycle using two of the colors, and use the third color on the long edges.
However, the faces of this embedding are not $4$-colorable. You can check that any two of the large faces of length $8$ are adjacent to each other (and therefore coloring all $5$ of these faces takes $5$ distinct colors).
answered Jan 21 at 3:49
Misha LavrovMisha Lavrov
47.2k657107
$endgroup$
$begingroup$
Thank you - this is perfect!
$endgroup$
– user101010
Jan 21 at 5:58
add a comment |
$begingroup$
Take a cellular embedding of $K_5$ in the torus, and turn it into a cubic graph by replacing each vertex by a $4$-cycle. Here's what this might look like:
The result is $3$-edge-colorable: color the edges of each $4$-cycle using two of the colors, and use the third color on the long edges.
However, the faces of this embedding are not $4$-colorable. You can check that any two of the large faces of length $8$ are adjacent to each other (and therefore coloring all $5$ of these faces takes $5$ distinct colors).
answered Jan 21 at 3:49
Misha LavrovMisha Lavrov
47.2k657107
$endgroup$
Take a cellular embedding of $K_5$ in the torus, and turn it into a cubic graph by replacing each vertex by a $4$-cycle. Here's what this might look like:
The result is $3$-edge-colorable: color the edges of each $4$-cycle using two of the colors, and use the third color on the long edges.
However, the faces of this embedding are not $4$-colorable. You can check that any two of the large faces of length $8$ are adjacent to each other (and therefore coloring all $5$ of these faces takes $5$ distinct colors).
answered Jan 21 at 3:49
Misha LavrovMisha Lavrov
47.2k657107
answered Jan 21 at 3:49
Misha LavrovMisha Lavrov
47.2k657107
answered Jan 21 at 3:49
Misha LavrovMisha Lavrov
47.2k657107
answered Jan 21 at 3:49
Misha LavrovMisha Lavrov
47.2k657107
47.2k657107
$begingroup$
Thank you - this is perfect!
$endgroup$
– user101010
Jan 21 at 5:58
add a comment |
$begingroup$
Thank you - this is perfect!
$endgroup$
– user101010
Jan 21 at 5:58
$begingroup$
Thank you - this is perfect!
$endgroup$
– user101010
Jan 21 at 5:58
$begingroup$
Thank you - this is perfect!
$endgroup$
– user101010
Jan 21 at 5:58
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%2f3081373%2f3-edge-colorable-cubic-graph-with-an-embedding-on-an-orientable-surface-that-is%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$
I think that for your first process to be correct, you also need the Graph $G$ to be bridgeless. This is the key point as you will never have an edge colored by (0,0) is $G$ is bridgeless, hence reducing to 3 colors. Otherwise this does not work.
$endgroup$
– Thomas Lesgourgues
Jan 21 at 11:45
$begingroup$
@ThomasLesgourgues You're right - without reading too carefully, I assumed that this was one of the things implied by "cellular embedding" (when there's a bridge, the face that's on both sides of that bridge is kind of awkward) but it's not (apparently it's not awkward enough, according to Wikipedia.) Although maybe we might not consider a graph where a face borders itself to be $4$-colorable, or colorable at all.
$endgroup$
– Misha Lavrov
Jan 21 at 17:44
$begingroup$
@ThomasLesgourgues The condition that the regions of the graph on the surface are 4-colorable implies that we don't have anything like that going on.
$endgroup$
– user101010
Jan 22 at 1:19
$begingroup$
@user101010. I think this is wrong, ANY planar graph is 4 face colorable, this is actually just the 4 color theorem. But you need the graph to be bridgeless in order to transfer the 4-face coloring into a 3-edge coloring. I might be wrong, happy to discuss
$endgroup$
– Thomas Lesgourgues
Jan 22 at 9:30