Montgomery's dynamic chromatic number conjecture for regular graphs

About 17 years old · traced to

Let GG be a regular graph. Its chromatic number is denoted by χ(G)\chi(G), and its dynamic chromatic number, the smallest number of colors in a dynamic proper vertex coloring, is denoted by χ2(G)\chi_2(G). Montgomery's conjecture.

χ2(G)−χ(G)≤2.\chi_2(G)-\chi(G)\leq 2.

The difference between dynamic chromatic number and chromatic number can be arbitrarily large for general graphs, so the regularity hypothesis is essential. The conjecture is resolved by the result cited in the source.

References

Primary source

Meysam Alishahi, “Dynamic Chromatic Number of Regular Graphs”, arXiv:1110.5140 (2011).

Additional references

3 papers in this index state this conjecture (2009–2011). The statement above is taken from the most recent of them; the others are arXiv:0911.4199, arXiv:0908.2543.

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.