We know the chromatic number of any planar graph is at most 4. (Every planar graph is 4 colorable.) My question is: at what number of added edges (If we add more edges to the planar graph) does a planar graph change its chromatic number (From 4 to 5, 6 or 7 . . .)? Or any suggestion regarding this.
K5 minus an edge is planar. If you add the missing edge, the graph becomes K5, which has chromatic number 5. But maybe I misunderstood the question.
We know that any planar graph with "n" vertices has a maximum of 3n - 6 edges and the chromatic number is 4. If we add more edges (we do not know up to what), this chromatic number changed to 5 or 6 or more and clearily the graph is not planar. My question "what is the minimum number of added edges to the planar graph that changes the chromatic number"?
Hi Asrat! It will depend on the graph. For a trivial example, if you start with a bipartite graph, you can make a triangle by adding just one edge, increasing the chromatic number to three.
This problem has been studied a lot from the 'dual' perspective of how many edges you must delete from a graph to change the chromatic number. This critical number of edges is called the chromatic edge stability number or chromatic edge stability index. If you type that into google scholar you will get a lot of results.
Wow!!! I want to advance those research papers and come up with specific deletion or addition, if God help me, for general and specific case. Thank you, professor. I will come back again after review those papers. Good!
The concept of adding edges to a planar graph to potentially change its chromatic number is an interesting one. In general, the chromatic number of a planar graph is at most 4, meaning that any planar graph can be colored with at most 4 colors such that no two adjacent vertices have the same color.
When additional edges are added to a planar graph, it is possible that the chromatic number may increase beyond 4. The exact point at which this change occurs can vary depending on the specific structure of the graph and the edges that are added.
One suggestion for exploring this concept is to analyze the impact of adding edges systematically to different types of planar graphs and observe how the chromatic number changes as a result. By conducting experiments and studying the resulting chromatic numbers, you may be able to identify patterns or thresholds at which the chromatic number increases beyond 4.
It is important to note that determining the exact number of added edges required to change the chromatic number of a planar graph may not have a straightforward answer and could depend on various factors such as the initial graph structure, the specific edges added, and the coloring algorithm used.
Overall, investigating the relationship between adding edges to planar graphs and changes in the chromatic number can provide valuable insights into the complexity of graph coloring and the behavior of planar graphs under graph modifications.
Of course, given any planar graph on at least 5 nodes, you can always increase the chromatic number to 5 by adding no more than 10 edges. Just take any 5 nodes and add the edges needed to form a clique of size 5.
If the planar graph is connected, we can say more. By computing a spanning tree, we can easily find a set of 5 nodes that induce a connected subgraph. Such a subgraph contains at least 4 edges. So, in this case, 6 additional edges suffice to increase the chromatic number to 5.
Yes! I appreciate you and I want to say "thank you" for your explanation. I have been doing all my efforts to come up with a good observation on this concept without ignoring a lot of papers that done before. Again I thank you professor. If you have any idea, please share me.
- Badges
- Science topic
- Similar topics
- Names