Mixing
$4$-degenerate Graph is $4$-colourable.
Clash Royale CLAN TAG#URR8PPP
up vote
0
down vote
favorite
A Graph $G$ is $k$-degenerate if every Subgraph $H subset G$ has at least one Vertex with degree $leq k$. I know how to easily show that these graphs are $5$-colourable via induction. Since $G$ is a subgraph of $G$ we have a vertex with degree at most $4$. Call this vertex $v$. Using the induction hypothesis on $G-v$ and adding $v$ back gives us the $5$-colourability. However, I do not know how to prove that these graphs are indeed $4$-colourable.
Furthermore, I have the question if the complete Graph $K_5$ is a $4$-degenerate graph, because there is no vertex with degree higher than $4$. However, this would result in an contradiction, would not it?
Thanks for your help.
graph-theory
asked Jul 22 at 23:15
Deavor
568513
add a comment |Â
up vote
0
down vote
favorite
A Graph $G$ is $k$-degenerate if every Subgraph $H subset G$ has at least one Vertex with degree $leq k$. I know how to easily show that these graphs are $5$-colourable via induction. Since $G$ is a subgraph of $G$ we have a vertex with degree at most $4$. Call this vertex $v$. Using the induction hypothesis on $G-v$ and adding $v$ back gives us the $5$-colourability. However, I do not know how to prove that these graphs are indeed $4$-colourable.
Furthermore, I have the question if the complete Graph $K_5$ is a $4$-degenerate graph, because there is no vertex with degree higher than $4$. However, this would result in an contradiction, would not it?
Thanks for your help.
graph-theory
asked Jul 22 at 23:15
Deavor
568513
add a comment |Â
up vote
0
down vote
favorite
up vote
0
down vote
favorite
A Graph $G$ is $k$-degenerate if every Subgraph $H subset G$ has at least one Vertex with degree $leq k$. I know how to easily show that these graphs are $5$-colourable via induction. Since $G$ is a subgraph of $G$ we have a vertex with degree at most $4$. Call this vertex $v$. Using the induction hypothesis on $G-v$ and adding $v$ back gives us the $5$-colourability. However, I do not know how to prove that these graphs are indeed $4$-colourable.
Furthermore, I have the question if the complete Graph $K_5$ is a $4$-degenerate graph, because there is no vertex with degree higher than $4$. However, this would result in an contradiction, would not it?
Thanks for your help.
graph-theory
asked Jul 22 at 23:15
Deavor
568513
A Graph $G$ is $k$-degenerate if every Subgraph $H subset G$ has at least one Vertex with degree $leq k$. I know how to easily show that these graphs are $5$-colourable via induction. Since $G$ is a subgraph of $G$ we have a vertex with degree at most $4$. Call this vertex $v$. Using the induction hypothesis on $G-v$ and adding $v$ back gives us the $5$-colourability. However, I do not know how to prove that these graphs are indeed $4$-colourable.
Furthermore, I have the question if the complete Graph $K_5$ is a $4$-degenerate graph, because there is no vertex with degree higher than $4$. However, this would result in an contradiction, would not it?
Thanks for your help.
graph-theory
asked Jul 22 at 23:15
Deavor
568513
asked Jul 22 at 23:15
Deavor
568513
asked Jul 22 at 23:15
Deavor
568513
asked Jul 22 at 23:15
Deavor
568513
568513
add a comment |Â
add a comment |Â
1 Answer
1
active
oldest
votes
up vote
2
down vote
accepted
Every $k$-degenerate graph is $k+1$-colourable, and this is best possible, as the complete graph $K_k+1$ shows. In other words, your reasoning is correct, and whoever told you that every $4$-degenerate graph is $4$-colourable was wrong. Is this an exercise in a book?
answered Jul 23 at 5:01
bof
45.9k348110
Actually it is an exercise from an old exam. So I thought $k=4$ could be an exception. It has to be a typo then. Unfortunately, I do not know what happened in the actual exam, but I think that it had to be corrected.
– Deavor
Jul 23 at 7:36
add a comment |Â
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
2
down vote
accepted
Every $k$-degenerate graph is $k+1$-colourable, and this is best possible, as the complete graph $K_k+1$ shows. In other words, your reasoning is correct, and whoever told you that every $4$-degenerate graph is $4$-colourable was wrong. Is this an exercise in a book?
answered Jul 23 at 5:01
bof
45.9k348110
Actually it is an exercise from an old exam. So I thought $k=4$ could be an exception. It has to be a typo then. Unfortunately, I do not know what happened in the actual exam, but I think that it had to be corrected.
– Deavor
Jul 23 at 7:36
add a comment |Â
up vote
2
down vote
accepted
Every $k$-degenerate graph is $k+1$-colourable, and this is best possible, as the complete graph $K_k+1$ shows. In other words, your reasoning is correct, and whoever told you that every $4$-degenerate graph is $4$-colourable was wrong. Is this an exercise in a book?
answered Jul 23 at 5:01
bof
45.9k348110
Actually it is an exercise from an old exam. So I thought $k=4$ could be an exception. It has to be a typo then. Unfortunately, I do not know what happened in the actual exam, but I think that it had to be corrected.
– Deavor
Jul 23 at 7:36
add a comment |Â
up vote
2
down vote
accepted
up vote
2
down vote
accepted
Every $k$-degenerate graph is $k+1$-colourable, and this is best possible, as the complete graph $K_k+1$ shows. In other words, your reasoning is correct, and whoever told you that every $4$-degenerate graph is $4$-colourable was wrong. Is this an exercise in a book?
answered Jul 23 at 5:01
bof
45.9k348110
Every $k$-degenerate graph is $k+1$-colourable, and this is best possible, as the complete graph $K_k+1$ shows. In other words, your reasoning is correct, and whoever told you that every $4$-degenerate graph is $4$-colourable was wrong. Is this an exercise in a book?
answered Jul 23 at 5:01
bof
45.9k348110
answered Jul 23 at 5:01
bof
45.9k348110
answered Jul 23 at 5:01
bof
45.9k348110
answered Jul 23 at 5:01
bof
45.9k348110
45.9k348110
Actually it is an exercise from an old exam. So I thought $k=4$ could be an exception. It has to be a typo then. Unfortunately, I do not know what happened in the actual exam, but I think that it had to be corrected.
– Deavor
Jul 23 at 7:36
add a comment |Â
Actually it is an exercise from an old exam. So I thought $k=4$ could be an exception. It has to be a typo then. Unfortunately, I do not know what happened in the actual exam, but I think that it had to be corrected.
– Deavor
Jul 23 at 7:36
Actually it is an exercise from an old exam. So I thought $k=4$ could be an exception. It has to be a typo then. Unfortunately, I do not know what happened in the actual exam, but I think that it had to be corrected.
– Deavor
Jul 23 at 7:36
Actually it is an exercise from an old exam. So I thought $k=4$ could be an exception. It has to be a typo then. Unfortunately, I do not know what happened in the actual exam, but I think that it had to be corrected.
– Deavor
Jul 23 at 7:36
add a comment |Â
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
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2859860%2f4-degenerate-graph-is-4-colourable%23new-answer', 'question_page');
);
Post as a guest
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
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
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