# On Coloring Resilient Graphs

DevFeed: [On Coloring Resilient Graphs](<https://devfeed.tech/articles/on-coloring-resilient-graphs-40346.md>)

Original publisher: [Read original article](<https://www.jeremykun.com/2014/02/21/on-coloring-resilient-graphs/>)

Published: 2014-02-21T08:45:39Z

Content type: article

Language: en

Sources: [Jeremy Kun](<https://devfeed.tech/sources/jeremy-kun.md>)

Topics: [Graphs](<https://devfeed.tech/topics/graphs.md>), [Algorithms](<https://devfeed.tech/topics/algorithms.md>)

Tags: [approximation-algorithms](<https://devfeed.tech/tags/approximation-algorithms.md>), [complexity](<https://devfeed.tech/tags/complexity.md>), [computational-complexity](<https://devfeed.tech/tags/computational-complexity.md>), [graph](<https://devfeed.tech/tags/graph.md>), [graph-coloring](<https://devfeed.tech/tags/graph-coloring.md>), [graphs](<https://devfeed.tech/tags/graphs.md>), [greedy-algorithm](<https://devfeed.tech/tags/greedy-algorithm.md>), [mathematics](<https://devfeed.tech/tags/mathematics.md>), [np-hard](<https://devfeed.tech/tags/np-hard.md>), [research](<https://devfeed.tech/tags/research.md>), [resilience](<https://devfeed.tech/tags/resilience.md>)

## AI overview

An informal explanation of graph coloring, including why deciding 3-colorability is considered NP-hard and several graph properties that can make coloring problems easier. The article also announces the author's paper on resilient graphs.

## Source excerpt

I'm pleased to announce that another paper of mine is finished. This one just got accepted to MFCS 2014, which is being held in Budapest this year (this whole research thing is exciting!). This is joint work with my advisor, Lev Reyzin. As with my first paper, I'd like to explain things here on my blog a bit more informally than a scholarly article allows. A Recent History of Graph Coloring One of the first important things you learn when you study graphs is that coloring graphs is hard.