Mixing
Prove that the Chromatic Number is Invariant under Isomorphism
Clash Royale CLAN TAG#URR8PPP
up vote
1
down vote
favorite
I have a "Which of the following graphs are isomorphic?" question. The graphs are the same order and regular, which makes it quite difficult for me to prove why they are isomorphic, or find out why they are not. One thing I recognized is that, one of them is 2 colorable whereas the other one is not. Please prove that chromatic number is invariant under isomorphism, so that I can prove these two graphs are not isomorphic.
I am still struggling with the other two graphs, so my other question is: if the order and degree sequence are the same; what could be other invariant that will help me to prove they are not isomorphic (such as chromatic number helping me)? If everything seems to be the same, what is the formal proof? I suppose showing that the two graphs have equivalent adjacency matrices?
graph-theory coloring graph-isomorphism
asked Jul 16 at 15:26
Ninja Bug
132
add a comment |Â
up vote
1
down vote
favorite
I have a "Which of the following graphs are isomorphic?" question. The graphs are the same order and regular, which makes it quite difficult for me to prove why they are isomorphic, or find out why they are not. One thing I recognized is that, one of them is 2 colorable whereas the other one is not. Please prove that chromatic number is invariant under isomorphism, so that I can prove these two graphs are not isomorphic.
I am still struggling with the other two graphs, so my other question is: if the order and degree sequence are the same; what could be other invariant that will help me to prove they are not isomorphic (such as chromatic number helping me)? If everything seems to be the same, what is the formal proof? I suppose showing that the two graphs have equivalent adjacency matrices?
graph-theory coloring graph-isomorphism
asked Jul 16 at 15:26
Ninja Bug
132
Hint: given a two-coloring of one graph, show that you can create a two-coloring of the other graph, supposing they are isomorphic.
– Wojowu
Jul 16 at 15:41
@Wojowu I do not understand what you mean, and there are multiple questions, which one are you referring to?
– Ninja Bug
Jul 18 at 13:58
I was refering to the question in the title, or more specifically, the fact that whether a graph is two-colorable should be preserved by isomorphisms (addressing the case of the two graphs you talk about in the first paragraph)
– Wojowu
Jul 18 at 14:04
@Wojowu okay, but this does not seem like a formal proof. We just show that there is a supporting example by doing that.
– Ninja Bug
Jul 18 at 14:08
add a comment |Â
up vote
1
down vote
favorite
up vote
1
down vote
favorite
I have a "Which of the following graphs are isomorphic?" question. The graphs are the same order and regular, which makes it quite difficult for me to prove why they are isomorphic, or find out why they are not. One thing I recognized is that, one of them is 2 colorable whereas the other one is not. Please prove that chromatic number is invariant under isomorphism, so that I can prove these two graphs are not isomorphic.
I am still struggling with the other two graphs, so my other question is: if the order and degree sequence are the same; what could be other invariant that will help me to prove they are not isomorphic (such as chromatic number helping me)? If everything seems to be the same, what is the formal proof? I suppose showing that the two graphs have equivalent adjacency matrices?
graph-theory coloring graph-isomorphism
asked Jul 16 at 15:26
Ninja Bug
132
I have a "Which of the following graphs are isomorphic?" question. The graphs are the same order and regular, which makes it quite difficult for me to prove why they are isomorphic, or find out why they are not. One thing I recognized is that, one of them is 2 colorable whereas the other one is not. Please prove that chromatic number is invariant under isomorphism, so that I can prove these two graphs are not isomorphic.
I am still struggling with the other two graphs, so my other question is: if the order and degree sequence are the same; what could be other invariant that will help me to prove they are not isomorphic (such as chromatic number helping me)? If everything seems to be the same, what is the formal proof? I suppose showing that the two graphs have equivalent adjacency matrices?
graph-theory coloring graph-isomorphism
asked Jul 16 at 15:26
Ninja Bug
132
asked Jul 16 at 15:26
Ninja Bug
132
asked Jul 16 at 15:26
Ninja Bug
132
asked Jul 16 at 15:26
Ninja Bug
132
132
Hint: given a two-coloring of one graph, show that you can create a two-coloring of the other graph, supposing they are isomorphic.
– Wojowu
Jul 16 at 15:41
@Wojowu I do not understand what you mean, and there are multiple questions, which one are you referring to?
– Ninja Bug
Jul 18 at 13:58
I was refering to the question in the title, or more specifically, the fact that whether a graph is two-colorable should be preserved by isomorphisms (addressing the case of the two graphs you talk about in the first paragraph)
– Wojowu
Jul 18 at 14:04
@Wojowu okay, but this does not seem like a formal proof. We just show that there is a supporting example by doing that.
– Ninja Bug
Jul 18 at 14:08
add a comment |Â
Hint: given a two-coloring of one graph, show that you can create a two-coloring of the other graph, supposing they are isomorphic.
– Wojowu
Jul 16 at 15:41
@Wojowu I do not understand what you mean, and there are multiple questions, which one are you referring to?
– Ninja Bug
Jul 18 at 13:58
I was refering to the question in the title, or more specifically, the fact that whether a graph is two-colorable should be preserved by isomorphisms (addressing the case of the two graphs you talk about in the first paragraph)
– Wojowu
Jul 18 at 14:04
@Wojowu okay, but this does not seem like a formal proof. We just show that there is a supporting example by doing that.
– Ninja Bug
Jul 18 at 14:08
Hint: given a two-coloring of one graph, show that you can create a two-coloring of the other graph, supposing they are isomorphic.
– Wojowu
Jul 16 at 15:41
Hint: given a two-coloring of one graph, show that you can create a two-coloring of the other graph, supposing they are isomorphic.
– Wojowu
Jul 16 at 15:41
@Wojowu I do not understand what you mean, and there are multiple questions, which one are you referring to?
– Ninja Bug
Jul 18 at 13:58
@Wojowu I do not understand what you mean, and there are multiple questions, which one are you referring to?
– Ninja Bug
Jul 18 at 13:58
I was refering to the question in the title, or more specifically, the fact that whether a graph is two-colorable should be preserved by isomorphisms (addressing the case of the two graphs you talk about in the first paragraph)
– Wojowu
Jul 18 at 14:04
I was refering to the question in the title, or more specifically, the fact that whether a graph is two-colorable should be preserved by isomorphisms (addressing the case of the two graphs you talk about in the first paragraph)
– Wojowu
Jul 18 at 14:04
@Wojowu okay, but this does not seem like a formal proof. We just show that there is a supporting example by doing that.
– Ninja Bug
Jul 18 at 14:08
@Wojowu okay, but this does not seem like a formal proof. We just show that there is a supporting example by doing that.
– Ninja Bug
Jul 18 at 14:08
add a comment |Â
active
oldest
votes
active
oldest
votes
active
oldest
votes
active
oldest
votes
active
oldest
votes
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%2f2853507%2fprove-that-the-chromatic-number-is-invariant-under-isomorphism%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
Hint: given a two-coloring of one graph, show that you can create a two-coloring of the other graph, supposing they are isomorphic.
– Wojowu
Jul 16 at 15:41
@Wojowu I do not understand what you mean, and there are multiple questions, which one are you referring to?
– Ninja Bug
Jul 18 at 13:58
I was refering to the question in the title, or more specifically, the fact that whether a graph is two-colorable should be preserved by isomorphisms (addressing the case of the two graphs you talk about in the first paragraph)
– Wojowu
Jul 18 at 14:04
@Wojowu okay, but this does not seem like a formal proof. We just show that there is a supporting example by doing that.
– Ninja Bug
Jul 18 at 14:08