Minimum number of colors needed to color the graph
$begingroup$
What is the chromatic number of the below graph?
I am preparing for a competitive exam, and I am required to solve questions in under 3 minutes.
Well, I first tried to color the graph using basic steps such as not giving any two adjacent vertices the same color. But with this approach, I sometimes end up with the wrong answer.
However, whenever I answer by counting the minimal number of largest maximal independent sets that cover all vertices of the graph, I do get the correct answer, but this approach takes time.
Please suggest a method for such types of problems so that the correct answer can be given in a reasonable amount of time.
graph-theory
edited Dec 25 '18 at 13:14
EdOverflow
25119
asked Dec 25 '18 at 12:28
user3767495user3767495
4078
$endgroup$
add a comment |
$begingroup$
What is the chromatic number of the below graph?
I am preparing for a competitive exam, and I am required to solve questions in under 3 minutes.
Well, I first tried to color the graph using basic steps such as not giving any two adjacent vertices the same color. But with this approach, I sometimes end up with the wrong answer.
However, whenever I answer by counting the minimal number of largest maximal independent sets that cover all vertices of the graph, I do get the correct answer, but this approach takes time.
Please suggest a method for such types of problems so that the correct answer can be given in a reasonable amount of time.
graph-theory
edited Dec 25 '18 at 13:14
EdOverflow
25119
asked Dec 25 '18 at 12:28
user3767495user3767495
4078
$endgroup$
$begingroup$
When trying $3$, there really isn't any choice. There are so many triangles that you're forced all the way.
$endgroup$
– Arthur
Dec 25 '18 at 12:43
add a comment |
$begingroup$
What is the chromatic number of the below graph?
I am preparing for a competitive exam, and I am required to solve questions in under 3 minutes.
Well, I first tried to color the graph using basic steps such as not giving any two adjacent vertices the same color. But with this approach, I sometimes end up with the wrong answer.
However, whenever I answer by counting the minimal number of largest maximal independent sets that cover all vertices of the graph, I do get the correct answer, but this approach takes time.
Please suggest a method for such types of problems so that the correct answer can be given in a reasonable amount of time.
graph-theory
edited Dec 25 '18 at 13:14
EdOverflow
25119
asked Dec 25 '18 at 12:28
user3767495user3767495
4078
$endgroup$
What is the chromatic number of the below graph?
I am preparing for a competitive exam, and I am required to solve questions in under 3 minutes.
Well, I first tried to color the graph using basic steps such as not giving any two adjacent vertices the same color. But with this approach, I sometimes end up with the wrong answer.
However, whenever I answer by counting the minimal number of largest maximal independent sets that cover all vertices of the graph, I do get the correct answer, but this approach takes time.
Please suggest a method for such types of problems so that the correct answer can be given in a reasonable amount of time.
graph-theory
graph-theory
edited Dec 25 '18 at 13:14
EdOverflow
25119
asked Dec 25 '18 at 12:28
user3767495user3767495
4078
edited Dec 25 '18 at 13:14
EdOverflow
25119
asked Dec 25 '18 at 12:28
user3767495user3767495
4078
edited Dec 25 '18 at 13:14
EdOverflow
25119
edited Dec 25 '18 at 13:14
EdOverflow
25119
edited Dec 25 '18 at 13:14
EdOverflow
25119
25119
asked Dec 25 '18 at 12:28
user3767495user3767495
4078
asked Dec 25 '18 at 12:28
user3767495user3767495
4078
asked Dec 25 '18 at 12:28
user3767495user3767495
4078
4078
$begingroup$
When trying $3$, there really isn't any choice. There are so many triangles that you're forced all the way.
$endgroup$
– Arthur
Dec 25 '18 at 12:43
add a comment |
$begingroup$
When trying $3$, there really isn't any choice. There are so many triangles that you're forced all the way.
$endgroup$
– Arthur
Dec 25 '18 at 12:43
$begingroup$
When trying $3$, there really isn't any choice. There are so many triangles that you're forced all the way.
$endgroup$
– Arthur
Dec 25 '18 at 12:43
$begingroup$
When trying $3$, there really isn't any choice. There are so many triangles that you're forced all the way.
$endgroup$
– Arthur
Dec 25 '18 at 12:43
add a comment |
2 Answers
2
active
oldest
votes
$begingroup$
For a more general answer, use $chi(G) = min{chi(G + uv), chi(G/uv)}$ where $u$ and $v$ are non-adjacent vertices and $G/uv$ denotes a contraction of $G$, obtained by identifying the vertices $u$ and $v$. The logic here is that if $u$ and $v$ have the same colour in a minimal colouring, we may as well contract them and this won't affect the minimal number of colours used, and if they have different colours then adding an edge between them won't affect the number of colours used. Since $u$ and $v$ either have the same colour or different colours, we just take the minimum between the two options.
In your case, since the neighbourhood of Ed is contained in the neighbourhood of Def, we should contract Ed and Def (and colour them both red), and similarly we should contract $Fra$ and $Fa$ (and colour them both blue). Continuing in this way, you end up with a complete graph on three vertices, which has chromatic number three.
answered Dec 25 '18 at 12:51
ODFODF
1,486510
$endgroup$
add a comment |
$begingroup$
This graph is planar so $leq 4$. But it is doable by $3$ colors.
It is not doable with $2$ colors since we have subgraph $K_3$.
answered Dec 25 '18 at 12:43
Maria MazurMaria Mazur
46.4k1260119
$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%2f3052071%2fminimum-number-of-colors-needed-to-color-the-graph%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
For a more general answer, use $chi(G) = min{chi(G + uv), chi(G/uv)}$ where $u$ and $v$ are non-adjacent vertices and $G/uv$ denotes a contraction of $G$, obtained by identifying the vertices $u$ and $v$. The logic here is that if $u$ and $v$ have the same colour in a minimal colouring, we may as well contract them and this won't affect the minimal number of colours used, and if they have different colours then adding an edge between them won't affect the number of colours used. Since $u$ and $v$ either have the same colour or different colours, we just take the minimum between the two options.
In your case, since the neighbourhood of Ed is contained in the neighbourhood of Def, we should contract Ed and Def (and colour them both red), and similarly we should contract $Fra$ and $Fa$ (and colour them both blue). Continuing in this way, you end up with a complete graph on three vertices, which has chromatic number three.
answered Dec 25 '18 at 12:51
ODFODF
1,486510
$endgroup$
add a comment |
$begingroup$
For a more general answer, use $chi(G) = min{chi(G + uv), chi(G/uv)}$ where $u$ and $v$ are non-adjacent vertices and $G/uv$ denotes a contraction of $G$, obtained by identifying the vertices $u$ and $v$. The logic here is that if $u$ and $v$ have the same colour in a minimal colouring, we may as well contract them and this won't affect the minimal number of colours used, and if they have different colours then adding an edge between them won't affect the number of colours used. Since $u$ and $v$ either have the same colour or different colours, we just take the minimum between the two options.
In your case, since the neighbourhood of Ed is contained in the neighbourhood of Def, we should contract Ed and Def (and colour them both red), and similarly we should contract $Fra$ and $Fa$ (and colour them both blue). Continuing in this way, you end up with a complete graph on three vertices, which has chromatic number three.
answered Dec 25 '18 at 12:51
ODFODF
1,486510
$endgroup$
add a comment |
$begingroup$
For a more general answer, use $chi(G) = min{chi(G + uv), chi(G/uv)}$ where $u$ and $v$ are non-adjacent vertices and $G/uv$ denotes a contraction of $G$, obtained by identifying the vertices $u$ and $v$. The logic here is that if $u$ and $v$ have the same colour in a minimal colouring, we may as well contract them and this won't affect the minimal number of colours used, and if they have different colours then adding an edge between them won't affect the number of colours used. Since $u$ and $v$ either have the same colour or different colours, we just take the minimum between the two options.
In your case, since the neighbourhood of Ed is contained in the neighbourhood of Def, we should contract Ed and Def (and colour them both red), and similarly we should contract $Fra$ and $Fa$ (and colour them both blue). Continuing in this way, you end up with a complete graph on three vertices, which has chromatic number three.
answered Dec 25 '18 at 12:51
ODFODF
1,486510
$endgroup$
For a more general answer, use $chi(G) = min{chi(G + uv), chi(G/uv)}$ where $u$ and $v$ are non-adjacent vertices and $G/uv$ denotes a contraction of $G$, obtained by identifying the vertices $u$ and $v$. The logic here is that if $u$ and $v$ have the same colour in a minimal colouring, we may as well contract them and this won't affect the minimal number of colours used, and if they have different colours then adding an edge between them won't affect the number of colours used. Since $u$ and $v$ either have the same colour or different colours, we just take the minimum between the two options.
In your case, since the neighbourhood of Ed is contained in the neighbourhood of Def, we should contract Ed and Def (and colour them both red), and similarly we should contract $Fra$ and $Fa$ (and colour them both blue). Continuing in this way, you end up with a complete graph on three vertices, which has chromatic number three.
answered Dec 25 '18 at 12:51
ODFODF
1,486510
answered Dec 25 '18 at 12:51
ODFODF
1,486510
answered Dec 25 '18 at 12:51
ODFODF
1,486510
answered Dec 25 '18 at 12:51
ODFODF
1,486510
1,486510
add a comment |
add a comment |
$begingroup$
This graph is planar so $leq 4$. But it is doable by $3$ colors.
It is not doable with $2$ colors since we have subgraph $K_3$.
answered Dec 25 '18 at 12:43
Maria MazurMaria Mazur
46.4k1260119
$endgroup$
add a comment |
$begingroup$
This graph is planar so $leq 4$. But it is doable by $3$ colors.
It is not doable with $2$ colors since we have subgraph $K_3$.
answered Dec 25 '18 at 12:43
Maria MazurMaria Mazur
46.4k1260119
$endgroup$
add a comment |
$begingroup$
This graph is planar so $leq 4$. But it is doable by $3$ colors.
It is not doable with $2$ colors since we have subgraph $K_3$.
answered Dec 25 '18 at 12:43
Maria MazurMaria Mazur
46.4k1260119
$endgroup$
This graph is planar so $leq 4$. But it is doable by $3$ colors.
It is not doable with $2$ colors since we have subgraph $K_3$.
answered Dec 25 '18 at 12:43
Maria MazurMaria Mazur
46.4k1260119
edited Dec 25 '18 at 12:49
answered Dec 25 '18 at 12:43
Maria MazurMaria Mazur
46.4k1260119
answered Dec 25 '18 at 12:43
Maria MazurMaria Mazur
46.4k1260119
answered Dec 25 '18 at 12:43
Maria MazurMaria Mazur
46.4k1260119
46.4k1260119
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%2f3052071%2fminimum-number-of-colors-needed-to-color-the-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
$begingroup$
When trying $3$, there really isn't any choice. There are so many triangles that you're forced all the way.
$endgroup$
– Arthur
Dec 25 '18 at 12:43