1
$\begingroup$

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!

Improve this question
$\endgroup$
6
  • 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.
    Commented Jan 16, 2019 at 1:30
  • $\begingroup$ I edited the question according to your suggestion. $\endgroup$
    – Isinlor
    Commented Jan 16, 2019 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
    Commented Jan 16, 2019 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
    Commented Jan 16, 2019 at 12:45
  • $\begingroup$ @j_random_hacker Sure but the question explicitly says that the cactus graph is just an example. $\endgroup$
    – David Richerby
    Commented Jan 16, 2019 at 13:38

1 Answer 1

Reset to default
3
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\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
    Commented Jan 16, 2019 at 17:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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