Mixing
Assign two colors to nodes in a graph with constraint
$begingroup$
Suppose I have a connected graph $G$, where each node has degree at least $d$.
Now I want to assign two colors (blue and red) to the nodes. The constraint is that for each node, there should be $k$ ($k<d$) red nodes in his neighborhood (including himself).
I am thinking a possible way to formulate this problem:
We can use a binary variable $x_i$ to denote the color assignment to node $i$, where $x_i = 1$ means assigning red. Then for each node, we can build a linear function with integer variables: the sum of that node's neighbors (including himself) should be $k$. As a result, we can build a system of linear equations with $n$ binary variables and $n$ equations. A solution to the system of equations should be a valid color assignment.
Then I have two questions:
First, is the above formulation correct?
Second, what are the possible solutions of the system of equations (note that the variables are integers)? Is there always a solution? Can we even decide if there is a solution?
combinatorics graph-theory computational-complexity coloring
asked Jan 31 at 17:31
ParadoxParadox
909
$endgroup$
add a comment |
$begingroup$
Suppose I have a connected graph $G$, where each node has degree at least $d$.
Now I want to assign two colors (blue and red) to the nodes. The constraint is that for each node, there should be $k$ ($k<d$) red nodes in his neighborhood (including himself).
I am thinking a possible way to formulate this problem:
We can use a binary variable $x_i$ to denote the color assignment to node $i$, where $x_i = 1$ means assigning red. Then for each node, we can build a linear function with integer variables: the sum of that node's neighbors (including himself) should be $k$. As a result, we can build a system of linear equations with $n$ binary variables and $n$ equations. A solution to the system of equations should be a valid color assignment.
Then I have two questions:
First, is the above formulation correct?
Second, what are the possible solutions of the system of equations (note that the variables are integers)? Is there always a solution? Can we even decide if there is a solution?
combinatorics graph-theory computational-complexity coloring
asked Jan 31 at 17:31
ParadoxParadox
909
$endgroup$
add a comment |
$begingroup$
Suppose I have a connected graph $G$, where each node has degree at least $d$.
Now I want to assign two colors (blue and red) to the nodes. The constraint is that for each node, there should be $k$ ($k<d$) red nodes in his neighborhood (including himself).
I am thinking a possible way to formulate this problem:
We can use a binary variable $x_i$ to denote the color assignment to node $i$, where $x_i = 1$ means assigning red. Then for each node, we can build a linear function with integer variables: the sum of that node's neighbors (including himself) should be $k$. As a result, we can build a system of linear equations with $n$ binary variables and $n$ equations. A solution to the system of equations should be a valid color assignment.
Then I have two questions:
First, is the above formulation correct?
Second, what are the possible solutions of the system of equations (note that the variables are integers)? Is there always a solution? Can we even decide if there is a solution?
combinatorics graph-theory computational-complexity coloring
asked Jan 31 at 17:31
ParadoxParadox
909
$endgroup$
Suppose I have a connected graph $G$, where each node has degree at least $d$.
Now I want to assign two colors (blue and red) to the nodes. The constraint is that for each node, there should be $k$ ($k<d$) red nodes in his neighborhood (including himself).
I am thinking a possible way to formulate this problem:
We can use a binary variable $x_i$ to denote the color assignment to node $i$, where $x_i = 1$ means assigning red. Then for each node, we can build a linear function with integer variables: the sum of that node's neighbors (including himself) should be $k$. As a result, we can build a system of linear equations with $n$ binary variables and $n$ equations. A solution to the system of equations should be a valid color assignment.
Then I have two questions:
First, is the above formulation correct?
Second, what are the possible solutions of the system of equations (note that the variables are integers)? Is there always a solution? Can we even decide if there is a solution?
combinatorics graph-theory computational-complexity coloring
combinatorics graph-theory computational-complexity coloring
asked Jan 31 at 17:31
ParadoxParadox
909
asked Jan 31 at 17:31
ParadoxParadox
909
asked Jan 31 at 17:31
ParadoxParadox
909
asked Jan 31 at 17:31
ParadoxParadox
909
asked Jan 31 at 17:31
ParadoxParadox
909
909
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
is the above formulation correct?
Yes.
what are the possible solutions of the system of equations... ?
They exactly correspond to the required colorings. I don’t see a different description of them.
Is there always a solution?
No. An example for $d=4$ and $k=1$ is the octahedron graph $O$. An example for $d=3$ and $k=2$ is a graph $O^-$ which is $O$ with one vertex removed. Indeed, since $O^-$ has a node adjacent to all other nodes of the graph, in $O^-$ should be exactly two red nodes. But then it is easy to check that there exists a node which neighborhood (including itself) contains at most one red node.
Can we even decide if there is a solution?
Yes, we can decide this by checking all $2^n$ possible vertex colorings of $G$. I don’t know whether is can be done faster, for instance, in polynomial time. This decicion problem may be NP-hard.
answered Feb 3 at 5:38
Alex RavskyAlex Ravsky
42.9k32483
$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%2f3095192%2fassign-two-colors-to-nodes-in-a-graph-with-constraint%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$
is the above formulation correct?
Yes.
what are the possible solutions of the system of equations... ?
They exactly correspond to the required colorings. I don’t see a different description of them.
Is there always a solution?
No. An example for $d=4$ and $k=1$ is the octahedron graph $O$. An example for $d=3$ and $k=2$ is a graph $O^-$ which is $O$ with one vertex removed. Indeed, since $O^-$ has a node adjacent to all other nodes of the graph, in $O^-$ should be exactly two red nodes. But then it is easy to check that there exists a node which neighborhood (including itself) contains at most one red node.
Can we even decide if there is a solution?
Yes, we can decide this by checking all $2^n$ possible vertex colorings of $G$. I don’t know whether is can be done faster, for instance, in polynomial time. This decicion problem may be NP-hard.
answered Feb 3 at 5:38
Alex RavskyAlex Ravsky
42.9k32483
$endgroup$
add a comment |
$begingroup$
is the above formulation correct?
Yes.
what are the possible solutions of the system of equations... ?
They exactly correspond to the required colorings. I don’t see a different description of them.
Is there always a solution?
No. An example for $d=4$ and $k=1$ is the octahedron graph $O$. An example for $d=3$ and $k=2$ is a graph $O^-$ which is $O$ with one vertex removed. Indeed, since $O^-$ has a node adjacent to all other nodes of the graph, in $O^-$ should be exactly two red nodes. But then it is easy to check that there exists a node which neighborhood (including itself) contains at most one red node.
Can we even decide if there is a solution?
Yes, we can decide this by checking all $2^n$ possible vertex colorings of $G$. I don’t know whether is can be done faster, for instance, in polynomial time. This decicion problem may be NP-hard.
answered Feb 3 at 5:38
Alex RavskyAlex Ravsky
42.9k32483
$endgroup$
add a comment |
$begingroup$
is the above formulation correct?
Yes.
what are the possible solutions of the system of equations... ?
They exactly correspond to the required colorings. I don’t see a different description of them.
Is there always a solution?
No. An example for $d=4$ and $k=1$ is the octahedron graph $O$. An example for $d=3$ and $k=2$ is a graph $O^-$ which is $O$ with one vertex removed. Indeed, since $O^-$ has a node adjacent to all other nodes of the graph, in $O^-$ should be exactly two red nodes. But then it is easy to check that there exists a node which neighborhood (including itself) contains at most one red node.
Can we even decide if there is a solution?
Yes, we can decide this by checking all $2^n$ possible vertex colorings of $G$. I don’t know whether is can be done faster, for instance, in polynomial time. This decicion problem may be NP-hard.
answered Feb 3 at 5:38
Alex RavskyAlex Ravsky
42.9k32483
$endgroup$
is the above formulation correct?
Yes.
what are the possible solutions of the system of equations... ?
They exactly correspond to the required colorings. I don’t see a different description of them.
Is there always a solution?
No. An example for $d=4$ and $k=1$ is the octahedron graph $O$. An example for $d=3$ and $k=2$ is a graph $O^-$ which is $O$ with one vertex removed. Indeed, since $O^-$ has a node adjacent to all other nodes of the graph, in $O^-$ should be exactly two red nodes. But then it is easy to check that there exists a node which neighborhood (including itself) contains at most one red node.
Can we even decide if there is a solution?
Yes, we can decide this by checking all $2^n$ possible vertex colorings of $G$. I don’t know whether is can be done faster, for instance, in polynomial time. This decicion problem may be NP-hard.
answered Feb 3 at 5:38
Alex RavskyAlex Ravsky
42.9k32483
edited Feb 3 at 7:48
answered Feb 3 at 5:38
Alex RavskyAlex Ravsky
42.9k32483
answered Feb 3 at 5:38
Alex RavskyAlex Ravsky
42.9k32483
answered Feb 3 at 5:38
Alex RavskyAlex Ravsky
42.9k32483
42.9k32483
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%2f3095192%2fassign-two-colors-to-nodes-in-a-graph-with-constraint%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
