# Reducing a graph without changing its chromatic number

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):

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!

• "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. Commented Jan 16, 2019 at 1:30
• I edited the question according to your suggestion. Commented Jan 16, 2019 at 10:32
• 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. Commented Jan 16, 2019 at 10:43
• 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. Commented Jan 16, 2019 at 12:45
• @j_random_hacker Sure but the question explicitly says that the cactus graph is just an example. Commented Jan 16, 2019 at 13:38

• 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$. Commented Jan 16, 2019 at 17:01