Question: In graph theory, contracting an edge or deleting an edge are basic operations in many topics such as graph minors or Wagner's theorem on planar graphs. And I'm interested in how these operations affect chromatic number, which is the smallest number of colors needed to color the vertices of a graph so that adjacent vertices have different colors.
Maybe... : My guess is that these operation never increases the chromatic number of any graph because, roughly speaking, contraction-deletion makes a graph 'less complicated'. (Excuse my sloppy expression.) For example, a planar graph is 4-colorable even after deletion-contraction operations because they preserve planairty.
Maybe not... : But pondering about Braess's paradox, which states that adding a route can cause overall traffic delays to worsen, I'm guessing this question may not be trivial at all and my intuition about deletion-contraction may be wrong.
- Is my question about chromatic number under deletion-contraction trivially true?
- If not, is there any paper about this topic?
- Is my conjecture true in a restricted setting, such as "A deletion-contraction operation in a planar graph never increases the chromatic number"?
