-3
$\begingroup$

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"?
Improve this question
$\endgroup$

1 Answer 1

Reset to default
4
$\begingroup$

Your question is trivially false. Contracting an edge in an even cycle increases the chromatic number. Deleting edges never increase the chromatic number however, a coloring stays a coloring after deleting an edge.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Arghhh, you're right. $\endgroup$
    – user19906
    Commented May 22, 2015 at 13:41

Not the answer you're looking for? Browse other questions tagged .