Prove that isomorphic graphs have the same chromatic number and the salllc" chromatic polynomial.
Answers
Answered by
0
This can be explained taking the following observation in consideration.
Suppose in a graph G₁ = (V₁, E₁) and G₂ = (V₂ - E₂)
V₁ ⇒ V₂ is a graph isomorphism between them. So a bi junction of vertices such that (v,w) ∈ E₁ if (f (v), f (w)) ∈ E₂.
If now c: V₁ ⇒ n = {1...n} is a vertex colouring of G₁ with n colours that check c ⁰ f ⁻¹ : V₂ ⇒ n is a vertex of a colouring of G₂. We can also transform a colouring c₁ on G₂ to one on G₁ via f as well. Use c¹ ° f.
The ismorphism ensures that valid colouring go to the same valid colouring that is with the same number of colours. These operations should be in each other's inverse so we have a bijection of colouring of G₁ and G₂ with a given number of colours.
As the chromatic polynomial only depends on the existence or number of colouring with a certain number of colours these must be the same for isomorphic graphs.
Suppose in a graph G₁ = (V₁, E₁) and G₂ = (V₂ - E₂)
V₁ ⇒ V₂ is a graph isomorphism between them. So a bi junction of vertices such that (v,w) ∈ E₁ if (f (v), f (w)) ∈ E₂.
If now c: V₁ ⇒ n = {1...n} is a vertex colouring of G₁ with n colours that check c ⁰ f ⁻¹ : V₂ ⇒ n is a vertex of a colouring of G₂. We can also transform a colouring c₁ on G₂ to one on G₁ via f as well. Use c¹ ° f.
The ismorphism ensures that valid colouring go to the same valid colouring that is with the same number of colours. These operations should be in each other's inverse so we have a bijection of colouring of G₁ and G₂ with a given number of colours.
As the chromatic polynomial only depends on the existence or number of colouring with a certain number of colours these must be the same for isomorphic graphs.
Answered by
0
Answer:
HOPE THE ABOVE GIVEN ATTACHMENT WILL HELP YOU........
Attachments:
Similar questions