pipette
ENEnglish

Dynamic Coloring and Graph Squares of Regular Graphs

Juan Gutierrez, Grover Ugarte

Preprint

En palabras de los autores

An -dynamic coloring of a graph is a proper vertex coloring in which every vertex sees at least distinct colors in its neighborhood. The minimum number of colors in such a coloring is the -dynamic chromatic number . We study dynamic colorings of regular graphs. A straighforward observation shows that , for any -regular graph . We prove that for every claw-free cubic graph , and the bound is sharp. For Hamiltonian claw-free cubic graphs, we improve the bound to apart from four explicit exceptions. We also determine exactly the -dynamic chromatic number of the -regular circulant graph for each . In particular, the case determines .

Resultado principalLimitación que admiten los autores

Apareció: jueves, 8 de octubre. arXiv. Preprint, todavía sin revisión por pares.

Comentario de los autores: 15 pages