Easy instances of the coloring problem on graphs with degree at most 4
$begingroup$
Given a graph with some set of colors, the goal of the coloring problem is to color the input graph with as few number of colors as possible, such that no adjacent vertices have the same color.
In general, the problem is hard. For trees and cycles, the problem is solvable in polynomial time. I am interested in bounded degree instances or more precisely graphs of degree at most 4. Is there any non-trivial subclass of graphs of degree at most 4 for which the coloring problem is solvable in polynomial time?
complexity-theory graphs colorings
edited 1 hour ago
Discrete lizard♦
4,21411435
asked 2 hours ago
I_wil_break_wallI_wil_break_wall
995
$endgroup$
add a comment |
$begingroup$
Given a graph with some set of colors, the goal of the coloring problem is to color the input graph with as few number of colors as possible, such that no adjacent vertices have the same color.
In general, the problem is hard. For trees and cycles, the problem is solvable in polynomial time. I am interested in bounded degree instances or more precisely graphs of degree at most 4. Is there any non-trivial subclass of graphs of degree at most 4 for which the coloring problem is solvable in polynomial time?
complexity-theory graphs colorings
edited 1 hour ago
Discrete lizard♦
4,21411435
asked 2 hours ago
I_wil_break_wallI_wil_break_wall
995
$endgroup$
add a comment |
$begingroup$
Given a graph with some set of colors, the goal of the coloring problem is to color the input graph with as few number of colors as possible, such that no adjacent vertices have the same color.
In general, the problem is hard. For trees and cycles, the problem is solvable in polynomial time. I am interested in bounded degree instances or more precisely graphs of degree at most 4. Is there any non-trivial subclass of graphs of degree at most 4 for which the coloring problem is solvable in polynomial time?
complexity-theory graphs colorings
edited 1 hour ago
Discrete lizard♦
4,21411435
asked 2 hours ago
I_wil_break_wallI_wil_break_wall
995
$endgroup$
Given a graph with some set of colors, the goal of the coloring problem is to color the input graph with as few number of colors as possible, such that no adjacent vertices have the same color.
In general, the problem is hard. For trees and cycles, the problem is solvable in polynomial time. I am interested in bounded degree instances or more precisely graphs of degree at most 4. Is there any non-trivial subclass of graphs of degree at most 4 for which the coloring problem is solvable in polynomial time?
complexity-theory graphs colorings
complexity-theory graphs colorings
edited 1 hour ago
Discrete lizard♦
4,21411435
asked 2 hours ago
I_wil_break_wallI_wil_break_wall
995
edited 1 hour ago
Discrete lizard♦
4,21411435
asked 2 hours ago
I_wil_break_wallI_wil_break_wall
995
edited 1 hour ago
Discrete lizard♦
4,21411435
edited 1 hour ago
Discrete lizard♦
4,21411435
edited 1 hour ago
Discrete lizard♦
4,21411435
4,21411435
asked 2 hours ago
I_wil_break_wallI_wil_break_wall
995
asked 2 hours ago
I_wil_break_wallI_wil_break_wall
995
asked 2 hours ago
I_wil_break_wallI_wil_break_wall
995
995
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
You can of course take any graph class for which coloring is easy, and additionally require that the maximum degree is at most 4. For example, every bipartite graph of maximum degree at most 4 works. Or "bipartite" could be replaced with say "outerplanar" or more generally "small cliquewidth".
But having maximum degree at most 4 alone will not work. That is, coloring remains hard for (i) 4-regular graphs and (ii) planar graphs of maximum degree 4.
answered 1 hour ago
JuhoJuho
15.4k54191
$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: "419"
};
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: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
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
},
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%2fcs.stackexchange.com%2fquestions%2f104496%2feasy-instances-of-the-coloring-problem-on-graphs-with-degree-at-most-4%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$
You can of course take any graph class for which coloring is easy, and additionally require that the maximum degree is at most 4. For example, every bipartite graph of maximum degree at most 4 works. Or "bipartite" could be replaced with say "outerplanar" or more generally "small cliquewidth".
But having maximum degree at most 4 alone will not work. That is, coloring remains hard for (i) 4-regular graphs and (ii) planar graphs of maximum degree 4.
answered 1 hour ago
JuhoJuho
15.4k54191
$endgroup$
add a comment |
$begingroup$
You can of course take any graph class for which coloring is easy, and additionally require that the maximum degree is at most 4. For example, every bipartite graph of maximum degree at most 4 works. Or "bipartite" could be replaced with say "outerplanar" or more generally "small cliquewidth".
But having maximum degree at most 4 alone will not work. That is, coloring remains hard for (i) 4-regular graphs and (ii) planar graphs of maximum degree 4.
answered 1 hour ago
JuhoJuho
15.4k54191
$endgroup$
add a comment |
$begingroup$
You can of course take any graph class for which coloring is easy, and additionally require that the maximum degree is at most 4. For example, every bipartite graph of maximum degree at most 4 works. Or "bipartite" could be replaced with say "outerplanar" or more generally "small cliquewidth".
But having maximum degree at most 4 alone will not work. That is, coloring remains hard for (i) 4-regular graphs and (ii) planar graphs of maximum degree 4.
answered 1 hour ago
JuhoJuho
15.4k54191
$endgroup$
You can of course take any graph class for which coloring is easy, and additionally require that the maximum degree is at most 4. For example, every bipartite graph of maximum degree at most 4 works. Or "bipartite" could be replaced with say "outerplanar" or more generally "small cliquewidth".
But having maximum degree at most 4 alone will not work. That is, coloring remains hard for (i) 4-regular graphs and (ii) planar graphs of maximum degree 4.
answered 1 hour ago
JuhoJuho
15.4k54191
answered 1 hour ago
JuhoJuho
15.4k54191
answered 1 hour ago
JuhoJuho
15.4k54191
answered 1 hour ago
JuhoJuho
15.4k54191
15.4k54191
add a comment |
add a comment |
Thanks for contributing an answer to Computer Science 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%2fcs.stackexchange.com%2fquestions%2f104496%2feasy-instances-of-the-coloring-problem-on-graphs-with-degree-at-most-4%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
