TOPICS
Search

Local Antimagic Chromatic Number


The local antimagic chromatic number chi_(la)(G) of a graph G is the minimum number of distinct induced vertex labels among all local antimagic labelings of G (Arumugam et al. 2017). It is defined whenever G admits such a labeling.

Since each local antimagic labeling induces a proper coloring,

 chi(G)<=chi_(la)(G)<=|V(G)|,
(1)

where chi(G) is the chromatic number and V(G) is the vertex set of G.

The two chromatic numbers need not be equal. For the graph disjoint union of three triangle graphs,

 chi_(la)(3C_3)=5,
(2)

whereas chi(3C_3)=3 (Chan et al. 2026, p. 255). The graph edge labels must be distinct across all three connected components, even though graph vertices in different components may have the same induced color.

For a connected graph G with at least three vertices and k leaves (vertices of vertex degree 1),

 chi_(la)(G)>=k+1.
(3)

This bound is sharp, with equality for star graphs (Lau et al. 2020, p. 1345).

For the complete bipartite graph K_(p,q) with q>=p>=1 and q>=2 (Lau et al. 2020, p. 1353),

 chi_(la)(K_(p,q))={q+1   p=1; 2   q>p>=2 and p=q  (mod2); 3   otherwise.
(4)

The leaf lower bound does not extend to a universal leaf-plus-two upper bound for trees. Brondani and França (2026) constructed a caterpillar graph with 40 leaves and 43 vertices for which chi_(la)(T)=43. More generally, for every integer r>=1, they constructed infinitely many caterpillar graphs with exactly r nonleaf vertices and

 chi_(la)(T)=l(T)+r=|V(T)|,
(5)

where l(T) is the number of leaves. Consequently, chi_(la)(T)-l(T) is unbounded even among caterpillar graphs (Brondani and França 2026).


See also

Antimagic Graph, Chromatic Number, Local Antimagic Graph, Local Antimagic Labeling, Vertex Coloring

Explore with Wolfram|Alpha

References

Arumugam, S.; Premalatha, K.; Bača, M.; and Semaničová-Feňovčíková, A. "Local Antimagic Vertex Coloring of a Graph." Graphs Combin. 33, 275-285, 2017. https://doi.org/10.1007/s00373-017-1758-7.Brondani, A. E. and França, F. A. M. "Counterexamples to the Local Antimagic Leaf Conjecture." 16 Oct 2026. https://arxiv.org/abs/2610.22783.Chan, T. L.; Shiu, W. C.; and Lau, G.-C. "On Local Antimagic Chromatic Number of Three Disjoint Cycles." J. Combin. Math. Combin. Comput. 131, 253-272, 2026. https://doi.org/10.61091/jcmcc131-13.Lau, G.-C.; Ng, H.-K.; and Shiu, W.-C. "Affirmative Solutions on Local Antimagic Chromatic Number." Graphs Combin. 36, 1337-1354, 2020. https://doi.org/10.1007/s00373-020-02197-2.

Cite this as:

Weisstein, Eric W. "Local Antimagic Chromatic Number." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/LocalAntimagicChromaticNumber.html

Subject classifications