Mixing
Relation between chromatic number and average degree
$begingroup$
In my lecture notes, I read that a graph G which has vertices whose average degree is at most $d$ is not $d + 1$ colorable. This seems counter-intuitive to me.
I have tried examples with various graphs and cycles between them (so each vertex has degree 2 and hence average degree is 2) to find a case to support the claim. But I can't seem to find any.
Is this a mistake in the lecture notes or am I just not seeing something obvious?
discrete-mathematics graph-theory coloring
edited Jan 25 at 5:23
gt6989b
35k22557
asked Jan 25 at 4:58
hussain sagarhussain sagar
908
$endgroup$
add a comment |
$begingroup$
In my lecture notes, I read that a graph G which has vertices whose average degree is at most $d$ is not $d + 1$ colorable. This seems counter-intuitive to me.
I have tried examples with various graphs and cycles between them (so each vertex has degree 2 and hence average degree is 2) to find a case to support the claim. But I can't seem to find any.
Is this a mistake in the lecture notes or am I just not seeing something obvious?
discrete-mathematics graph-theory coloring
edited Jan 25 at 5:23
gt6989b
35k22557
asked Jan 25 at 4:58
hussain sagarhussain sagar
908
$endgroup$
1
$begingroup$
I don't understand the claim. Is it saying that every graph $G$ with average degree $le d$ has chromatic number $gt d+1$? This is clearly false, any graph with no edges is a counterexample. Or is it saying that there exists a graph $G$ with average degree $le d$ and chromatic number $gt d+1$? This is trivially true; just take a graph of chromatic number $d+2$ and add enough isolated vertices to lower the average degree to $le d$. I think you must have left out some assumption.
$endgroup$
– bof
Jan 25 at 5:09
$begingroup$
From the text: An undirected graph $G$ with an average degree of at most $d$ cannot be coloured using $d+1$ colours. I think the text is referring to any graph G is not $d+1$ colourable if the average degree is at most $d$. As for your examples, a graph with no edges has an average degree 0 (d)and it's chromatic number is 1 (d+1) so it holds.
$endgroup$
– hussain sagar
Jan 25 at 5:42
$begingroup$
What do you mean, it holds? The text says "is not $d+1$ colourable"; if we set $d=0$ the graph with no edges is $d+1$ colourable. Moreover, "at most $d$" means $le d$; a graph with no edges has average degree $0$ which is certainly "at most $500$", but it is $501$ colourable.
$endgroup$
– bof
Jan 25 at 5:51
$begingroup$
My bad, I got confused. But basically, the question boils down to: Can you colour a graph with d + 1 colours, if the average degree is at most d? I am sorry for making it confusing.
$endgroup$
– hussain sagar
Jan 25 at 6:15
$begingroup$
I already gave the counterexample: just take a graph of chromatic number $d+2$ and add enough isolated vertices to lower the average degree to $le d$.
$endgroup$
– bof
Jan 25 at 6:48
add a comment |
$begingroup$
In my lecture notes, I read that a graph G which has vertices whose average degree is at most $d$ is not $d + 1$ colorable. This seems counter-intuitive to me.
I have tried examples with various graphs and cycles between them (so each vertex has degree 2 and hence average degree is 2) to find a case to support the claim. But I can't seem to find any.
Is this a mistake in the lecture notes or am I just not seeing something obvious?
discrete-mathematics graph-theory coloring
edited Jan 25 at 5:23
gt6989b
35k22557
asked Jan 25 at 4:58
hussain sagarhussain sagar
908
$endgroup$
In my lecture notes, I read that a graph G which has vertices whose average degree is at most $d$ is not $d + 1$ colorable. This seems counter-intuitive to me.
I have tried examples with various graphs and cycles between them (so each vertex has degree 2 and hence average degree is 2) to find a case to support the claim. But I can't seem to find any.
Is this a mistake in the lecture notes or am I just not seeing something obvious?
discrete-mathematics graph-theory coloring
discrete-mathematics graph-theory coloring
edited Jan 25 at 5:23
gt6989b
35k22557
asked Jan 25 at 4:58
hussain sagarhussain sagar
908
edited Jan 25 at 5:23
gt6989b
35k22557
asked Jan 25 at 4:58
hussain sagarhussain sagar
908
edited Jan 25 at 5:23
gt6989b
35k22557
edited Jan 25 at 5:23
gt6989b
35k22557
edited Jan 25 at 5:23
gt6989b
35k22557
35k22557
asked Jan 25 at 4:58
hussain sagarhussain sagar
908
asked Jan 25 at 4:58
hussain sagarhussain sagar
908
asked Jan 25 at 4:58
hussain sagarhussain sagar
908
908
1
$begingroup$
I don't understand the claim. Is it saying that every graph $G$ with average degree $le d$ has chromatic number $gt d+1$? This is clearly false, any graph with no edges is a counterexample. Or is it saying that there exists a graph $G$ with average degree $le d$ and chromatic number $gt d+1$? This is trivially true; just take a graph of chromatic number $d+2$ and add enough isolated vertices to lower the average degree to $le d$. I think you must have left out some assumption.
$endgroup$
– bof
Jan 25 at 5:09
$begingroup$
From the text: An undirected graph $G$ with an average degree of at most $d$ cannot be coloured using $d+1$ colours. I think the text is referring to any graph G is not $d+1$ colourable if the average degree is at most $d$. As for your examples, a graph with no edges has an average degree 0 (d)and it's chromatic number is 1 (d+1) so it holds.
$endgroup$
– hussain sagar
Jan 25 at 5:42
$begingroup$
What do you mean, it holds? The text says "is not $d+1$ colourable"; if we set $d=0$ the graph with no edges is $d+1$ colourable. Moreover, "at most $d$" means $le d$; a graph with no edges has average degree $0$ which is certainly "at most $500$", but it is $501$ colourable.
$endgroup$
– bof
Jan 25 at 5:51
$begingroup$
My bad, I got confused. But basically, the question boils down to: Can you colour a graph with d + 1 colours, if the average degree is at most d? I am sorry for making it confusing.
$endgroup$
– hussain sagar
Jan 25 at 6:15
$begingroup$
I already gave the counterexample: just take a graph of chromatic number $d+2$ and add enough isolated vertices to lower the average degree to $le d$.
$endgroup$
– bof
Jan 25 at 6:48
add a comment |
1
$begingroup$
I don't understand the claim. Is it saying that every graph $G$ with average degree $le d$ has chromatic number $gt d+1$? This is clearly false, any graph with no edges is a counterexample. Or is it saying that there exists a graph $G$ with average degree $le d$ and chromatic number $gt d+1$? This is trivially true; just take a graph of chromatic number $d+2$ and add enough isolated vertices to lower the average degree to $le d$. I think you must have left out some assumption.
$endgroup$
– bof
Jan 25 at 5:09
$begingroup$
From the text: An undirected graph $G$ with an average degree of at most $d$ cannot be coloured using $d+1$ colours. I think the text is referring to any graph G is not $d+1$ colourable if the average degree is at most $d$. As for your examples, a graph with no edges has an average degree 0 (d)and it's chromatic number is 1 (d+1) so it holds.
$endgroup$
– hussain sagar
Jan 25 at 5:42
$begingroup$
What do you mean, it holds? The text says "is not $d+1$ colourable"; if we set $d=0$ the graph with no edges is $d+1$ colourable. Moreover, "at most $d$" means $le d$; a graph with no edges has average degree $0$ which is certainly "at most $500$", but it is $501$ colourable.
$endgroup$
– bof
Jan 25 at 5:51
$begingroup$
My bad, I got confused. But basically, the question boils down to: Can you colour a graph with d + 1 colours, if the average degree is at most d? I am sorry for making it confusing.
$endgroup$
– hussain sagar
Jan 25 at 6:15
$begingroup$
I already gave the counterexample: just take a graph of chromatic number $d+2$ and add enough isolated vertices to lower the average degree to $le d$.
$endgroup$
– bof
Jan 25 at 6:48
1
1
$begingroup$
I don't understand the claim. Is it saying that every graph $G$ with average degree $le d$ has chromatic number $gt d+1$? This is clearly false, any graph with no edges is a counterexample. Or is it saying that there exists a graph $G$ with average degree $le d$ and chromatic number $gt d+1$? This is trivially true; just take a graph of chromatic number $d+2$ and add enough isolated vertices to lower the average degree to $le d$. I think you must have left out some assumption.
$endgroup$
– bof
Jan 25 at 5:09
$begingroup$
I don't understand the claim. Is it saying that every graph $G$ with average degree $le d$ has chromatic number $gt d+1$? This is clearly false, any graph with no edges is a counterexample. Or is it saying that there exists a graph $G$ with average degree $le d$ and chromatic number $gt d+1$? This is trivially true; just take a graph of chromatic number $d+2$ and add enough isolated vertices to lower the average degree to $le d$. I think you must have left out some assumption.
$endgroup$
– bof
Jan 25 at 5:09
$begingroup$
From the text: An undirected graph $G$ with an average degree of at most $d$ cannot be coloured using $d+1$ colours. I think the text is referring to any graph G is not $d+1$ colourable if the average degree is at most $d$. As for your examples, a graph with no edges has an average degree 0 (d)and it's chromatic number is 1 (d+1) so it holds.
$endgroup$
– hussain sagar
Jan 25 at 5:42
$begingroup$
From the text: An undirected graph $G$ with an average degree of at most $d$ cannot be coloured using $d+1$ colours. I think the text is referring to any graph G is not $d+1$ colourable if the average degree is at most $d$. As for your examples, a graph with no edges has an average degree 0 (d)and it's chromatic number is 1 (d+1) so it holds.
$endgroup$
– hussain sagar
Jan 25 at 5:42
$begingroup$
What do you mean, it holds? The text says "is not $d+1$ colourable"; if we set $d=0$ the graph with no edges is $d+1$ colourable. Moreover, "at most $d$" means $le d$; a graph with no edges has average degree $0$ which is certainly "at most $500$", but it is $501$ colourable.
$endgroup$
– bof
Jan 25 at 5:51
$begingroup$
What do you mean, it holds? The text says "is not $d+1$ colourable"; if we set $d=0$ the graph with no edges is $d+1$ colourable. Moreover, "at most $d$" means $le d$; a graph with no edges has average degree $0$ which is certainly "at most $500$", but it is $501$ colourable.
$endgroup$
– bof
Jan 25 at 5:51
$begingroup$
My bad, I got confused. But basically, the question boils down to: Can you colour a graph with d + 1 colours, if the average degree is at most d? I am sorry for making it confusing.
$endgroup$
– hussain sagar
Jan 25 at 6:15
$begingroup$
My bad, I got confused. But basically, the question boils down to: Can you colour a graph with d + 1 colours, if the average degree is at most d? I am sorry for making it confusing.
$endgroup$
– hussain sagar
Jan 25 at 6:15
$begingroup$
I already gave the counterexample: just take a graph of chromatic number $d+2$ and add enough isolated vertices to lower the average degree to $le d$.
$endgroup$
– bof
Jan 25 at 6:48
$begingroup$
I already gave the counterexample: just take a graph of chromatic number $d+2$ and add enough isolated vertices to lower the average degree to $le d$.
$endgroup$
– bof
Jan 25 at 6:48
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
There is no relationship between chromatic number and average degree.
On one hand, a graph with chromatic number $2$ can have arbitrarily large average degree. Just consider the complete bipartite graph $K_{n,n}$: this has average degree $n$, but chromatic number $2$.
On the other hand, you can take any graph with chromatic number $k$ and reduce its average degree to an arbitrarily small number by adding many isolated vertices. If your starting graph has $n$ vertices, it has at most $binom n2$ edges. By adding $tbinom n2 -n$ more isolated vertices, you reduce the average degree to at most $frac{2binom n2}{t binom n2} = frac2t$, which can be made as small as you want.
answered Jan 25 at 6:33
Misha LavrovMisha Lavrov
47.7k657107
$endgroup$
$begingroup$
I see that intuitively, but could you provide a numerical example for the same? I have been searching for one but have been unable to find one.
$endgroup$
– hussain sagar
Jan 25 at 6:35
$begingroup$
I have edited my answer; does this help?
$endgroup$
– Misha Lavrov
Jan 25 at 6:40
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%2f3086724%2frelation-between-chromatic-number-and-average-degree%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$
There is no relationship between chromatic number and average degree.
On one hand, a graph with chromatic number $2$ can have arbitrarily large average degree. Just consider the complete bipartite graph $K_{n,n}$: this has average degree $n$, but chromatic number $2$.
On the other hand, you can take any graph with chromatic number $k$ and reduce its average degree to an arbitrarily small number by adding many isolated vertices. If your starting graph has $n$ vertices, it has at most $binom n2$ edges. By adding $tbinom n2 -n$ more isolated vertices, you reduce the average degree to at most $frac{2binom n2}{t binom n2} = frac2t$, which can be made as small as you want.
answered Jan 25 at 6:33
Misha LavrovMisha Lavrov
47.7k657107
$endgroup$
$begingroup$
I see that intuitively, but could you provide a numerical example for the same? I have been searching for one but have been unable to find one.
$endgroup$
– hussain sagar
Jan 25 at 6:35
$begingroup$
I have edited my answer; does this help?
$endgroup$
– Misha Lavrov
Jan 25 at 6:40
add a comment |
$begingroup$
There is no relationship between chromatic number and average degree.
On one hand, a graph with chromatic number $2$ can have arbitrarily large average degree. Just consider the complete bipartite graph $K_{n,n}$: this has average degree $n$, but chromatic number $2$.
On the other hand, you can take any graph with chromatic number $k$ and reduce its average degree to an arbitrarily small number by adding many isolated vertices. If your starting graph has $n$ vertices, it has at most $binom n2$ edges. By adding $tbinom n2 -n$ more isolated vertices, you reduce the average degree to at most $frac{2binom n2}{t binom n2} = frac2t$, which can be made as small as you want.
answered Jan 25 at 6:33
Misha LavrovMisha Lavrov
47.7k657107
$endgroup$
$begingroup$
I see that intuitively, but could you provide a numerical example for the same? I have been searching for one but have been unable to find one.
$endgroup$
– hussain sagar
Jan 25 at 6:35
$begingroup$
I have edited my answer; does this help?
$endgroup$
– Misha Lavrov
Jan 25 at 6:40
add a comment |
$begingroup$
There is no relationship between chromatic number and average degree.
On one hand, a graph with chromatic number $2$ can have arbitrarily large average degree. Just consider the complete bipartite graph $K_{n,n}$: this has average degree $n$, but chromatic number $2$.
On the other hand, you can take any graph with chromatic number $k$ and reduce its average degree to an arbitrarily small number by adding many isolated vertices. If your starting graph has $n$ vertices, it has at most $binom n2$ edges. By adding $tbinom n2 -n$ more isolated vertices, you reduce the average degree to at most $frac{2binom n2}{t binom n2} = frac2t$, which can be made as small as you want.
answered Jan 25 at 6:33
Misha LavrovMisha Lavrov
47.7k657107
$endgroup$
There is no relationship between chromatic number and average degree.
On one hand, a graph with chromatic number $2$ can have arbitrarily large average degree. Just consider the complete bipartite graph $K_{n,n}$: this has average degree $n$, but chromatic number $2$.
On the other hand, you can take any graph with chromatic number $k$ and reduce its average degree to an arbitrarily small number by adding many isolated vertices. If your starting graph has $n$ vertices, it has at most $binom n2$ edges. By adding $tbinom n2 -n$ more isolated vertices, you reduce the average degree to at most $frac{2binom n2}{t binom n2} = frac2t$, which can be made as small as you want.
answered Jan 25 at 6:33
Misha LavrovMisha Lavrov
47.7k657107
edited Jan 25 at 15:10
answered Jan 25 at 6:33
Misha LavrovMisha Lavrov
47.7k657107
answered Jan 25 at 6:33
Misha LavrovMisha Lavrov
47.7k657107
answered Jan 25 at 6:33
Misha LavrovMisha Lavrov
47.7k657107
47.7k657107
$begingroup$
I see that intuitively, but could you provide a numerical example for the same? I have been searching for one but have been unable to find one.
$endgroup$
– hussain sagar
Jan 25 at 6:35
$begingroup$
I have edited my answer; does this help?
$endgroup$
– Misha Lavrov
Jan 25 at 6:40
add a comment |
$begingroup$
I see that intuitively, but could you provide a numerical example for the same? I have been searching for one but have been unable to find one.
$endgroup$
– hussain sagar
Jan 25 at 6:35
$begingroup$
I have edited my answer; does this help?
$endgroup$
– Misha Lavrov
Jan 25 at 6:40
$begingroup$
I see that intuitively, but could you provide a numerical example for the same? I have been searching for one but have been unable to find one.
$endgroup$
– hussain sagar
Jan 25 at 6:35
$begingroup$
I see that intuitively, but could you provide a numerical example for the same? I have been searching for one but have been unable to find one.
$endgroup$
– hussain sagar
Jan 25 at 6:35
$begingroup$
I have edited my answer; does this help?
$endgroup$
– Misha Lavrov
Jan 25 at 6:40
$begingroup$
I have edited my answer; does this help?
$endgroup$
– Misha Lavrov
Jan 25 at 6:40
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%2f3086724%2frelation-between-chromatic-number-and-average-degree%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
1
$begingroup$
I don't understand the claim. Is it saying that every graph $G$ with average degree $le d$ has chromatic number $gt d+1$? This is clearly false, any graph with no edges is a counterexample. Or is it saying that there exists a graph $G$ with average degree $le d$ and chromatic number $gt d+1$? This is trivially true; just take a graph of chromatic number $d+2$ and add enough isolated vertices to lower the average degree to $le d$. I think you must have left out some assumption.
$endgroup$
– bof
Jan 25 at 5:09
$begingroup$
From the text: An undirected graph $G$ with an average degree of at most $d$ cannot be coloured using $d+1$ colours. I think the text is referring to any graph G is not $d+1$ colourable if the average degree is at most $d$. As for your examples, a graph with no edges has an average degree 0 (d)and it's chromatic number is 1 (d+1) so it holds.
$endgroup$
– hussain sagar
Jan 25 at 5:42
$begingroup$
What do you mean, it holds? The text says "is not $d+1$ colourable"; if we set $d=0$ the graph with no edges is $d+1$ colourable. Moreover, "at most $d$" means $le d$; a graph with no edges has average degree $0$ which is certainly "at most $500$", but it is $501$ colourable.
$endgroup$
– bof
Jan 25 at 5:51
$begingroup$
My bad, I got confused. But basically, the question boils down to: Can you colour a graph with d + 1 colours, if the average degree is at most d? I am sorry for making it confusing.
$endgroup$
– hussain sagar
Jan 25 at 6:15
$begingroup$
I already gave the counterexample: just take a graph of chromatic number $d+2$ and add enough isolated vertices to lower the average degree to $le d$.
$endgroup$
– bof
Jan 25 at 6:48