Does reducing a graph (removing or replacing vertices or edges) without changing its chromatic number has a specific name?

Take this cactus graph as an example (although my question is about an arbitrary graph):

a cactus graph

The edges with vertex of degree 1 could be removed without affecting the vertex chromatic number. I think something similar should be possible with cycles e.g. removing the two vertices in the bottom of the cactus should not affect its chromatic number.

Are there polynomial algorithms that removes edges to the extent that no more edge can be removed without affecting an arbitrary graph chromatic number? I would prefer not to reinvent the wheel.

If the answer is no, are there algorithms that remove an arbitrary number of edges without affecting an arbitrary graph chromatic number?

My goal is to simplify graphs before feeding them into other algorithms.

I will also appreciate references to relevant literature. Thank you!

  • 1
    $\begingroup$ "Are there polynomial algorithms that do that?" It looks like you are not asking for a definition for "that". However, no definition can be found. Without a definition, it will not easy to identify a good or acceptable answer. How about "Are there polynomial algorithms that removes edges to the extent that no more edge can be removed without affecting its chromatic number?" Or "Are there polynomial algorithms that remove maximum number of edges without affecting its chromatic number?" Please update the question instead of comment here. $\endgroup$ – John L. Jan 16 '19 at 1:30
  • $\begingroup$ I edited the question according to your suggestion. $\endgroup$ – Isinlor Jan 16 '19 at 10:32
  • $\begingroup$ To be honest, my problem is that I have no formal education in graph theory and I don't know proper definition of the process that I'm describing. Also, I was unable to find the name and definition trough Google. Hence, my question here. I would appreciate even a keyword so that I can Google it and educate myself. Thank you. $\endgroup$ – Isinlor Jan 16 '19 at 10:43
  • 1
    $\begingroup$ If all the cycles in a cactus graph are even, then the graph is bipartite (can be coloured with 2 colours). If not, it can be coloured with 3 colours. $\endgroup$ – j_random_hacker Jan 16 '19 at 12:45
  • $\begingroup$ @j_random_hacker Sure but the question explicitly says that the cactus graph is just an example. $\endgroup$ – David Richerby Jan 16 '19 at 13:38

The general idea of taking a problem instance and reducing it to a smaller one that gives the same answer is called kernelization. It's widely used in parameterized complexity theory and not just for colourings.

  • $\begingroup$ A kernel is allowed to be give a "smaller" answer, provided that the answer to the original question can be inferred from it. In fact a kernel can even produce a bigger instance -- provided its size is bounded by some function of the parameters of interest, and independent of the original problem size $n$. $\endgroup$ – j_random_hacker Jan 16 '19 at 17:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.