Uniquely proper distinguishing colorable graphs
Abstract
A proper vertex-coloring of a graph G is called distinguishing, if the only automorphism preserving the colors is the identity. The minimum number of colors for such a coloring is denoted by χD(G). We say a graph G is uniquely proper distinguishing colorable (UPDC, for short) if and only if there exists only one partition of V(G) into χD(G) independent sets such that the identity is the only automorphism of G preserving the partition.
In this paper, we study the UPDC graphs. We show that a disconnected graph is UPDC if and only if it is the union of two isomorphic asymmetric connected bipartite graphs. We prove some results on bipartite UPDC graphs and show that any UPDC tree is one of the following: (i) an asymmetric tree, (ii) a tree with precisely one non-trivial automorphism and center xy such that this automorphism interchanges x and y, (iii) a star graph. Additional, a characterization of all graphs G of order n with the property that χD(G∪G) = χD(G) = k, where k=n-2, n-1, n, is given in this paper. Finally, we determine all graphs G of order n with the property that χD(G∪G) = χD(G)+1 = ℓ, where ℓ=n-1, n, n+1.
Keywords
Full Text:
PDFDOI: http://dx.doi.org/10.5614/ejgta.2025.13.2.15
References
B. Ahmadi, F. Alinaghipour, and M.H. Shekarriz, Number of distinguishing colorings and partitions, Discrete Math. 343(9) (2020), 111984.
M.O. Albertson and K.L. Collins, Symmetry Breaking in Graphs, Electron. J. Combin. 3(1) (1996), #R18.
S. Alikhani and S. Soltani, Distinguishing index of Kronecker product of two graphs, Electron. J. Graph Theory Appl. 9(1) (2021), 77–85.
L. Babai, Asymmetric trees with two prescribed degrees, Acta Math. Hung., 29(1–2) (1977), 193–200.
L. Babai, Asymmetric coloring of locally finite graphs and profinite permutation groups: Tucker's Conjecture confirmed, J. Algebra 607 (2022), 64–106.
R. F. Bailey and P. J. Cameron, Base size, metric dimension and other invariants of groups and graphs, Bull. Lond. Math. Soc. 43(2) (2011), 209–242.
B. Bollobás and N. Sauer, Uniquely colorable graphs with large girth, Canad. J. Math. 28 (1976), 1340–1344.
D. Cartwright and F. Harary, On the coloring of signed graphs, Elem. Math. 23 (1968), 85–89.
M. Cavers and K. Seyffarth, Graphs with large distinguishing chromatic number, Electron. J. Combin. 20(1) (2013), #P19.
M. Chan, The distinguishing number of the direct product and wreath product action, J. Algebraic Combin. 24, (2006), 331–345.
C.Y. Chao and Z. Chen, On uniquely 3-colorable graphs, Discrete Math., 112 (1993), 21–27.
G. Chartrand and P. Zhang, Chromatic Graph Theory, Chapman & Hall/CRC Press, Boca Raton, FL, 2009.
K.L. Collins and A.N. Trenk, The Distinguishing Chromatic Number, Electron. J. Combin. 13 (2006), #R16.
K.L. Collins and A.N. Trenk, The Distinguishing Number and Distinguishing Chromatic Number for Posets, Order 39 (2022), 361–380.
F. Harary, S.T. Hedetniemi, and R.W. Robinson, Uniquely colorable graphs, J. Combin. Theory 6 (1969), 264–270.
W. Imrich and S. Klavžar, Distinguishing Cartesian powers of graphs, J. Graph Theory 53 (2006), 250–260.
S. Klavžar, T.L. Wong, and X. Zhu, Distinguishing labellings of group action on vector spaces and graphs, J. Algebra 303 (2006), 626–641.
R. Kalinowski and M. Pilśniak, Proper distinguishing arc-colourings of symmetric digraphs, Appl. Math. Comput. 421 (2022).
R. Kalinowski, M. Pilśniak and M. Prorok, Distinguishing arc-colourings of symmetric digraphs, Art Discrete Appl. Math. 6 (2023), #P2.04.
M. Korivand, D.A. Mojdeh, E.T. Baskoro, and A. Erfanian, Edge-locating coloring of graphs, Electron. J. Graph Theory Appl. 12(1) (2024), 55–73.
F. Lehner, M. Pilśniak, and M. Stawiski, Distinguishing infinite graphs with bounded degrees, J. Graph Theory 101(1) (2022), 52–65.
K. Meslem and E. Sopena, Distinguishing numbers and distinguishing indices of oriented graphs, Discrete Appl. Math. 285 (2020), 330–342.
A. Russell and R. Sundaram, A note on the asymptotics and computational complexity of graph distinguishability, Electron. J. Combin. 5 (1998), #R23.
M.H. Shekarriz, B. Ahmadi, S.A. Talebpour and M. H. Shirdareh Haghighi, Distinguishing threshold of graphs, J. Graph Theory, 103(2) (2023), 359–377.
T.W. Tucker, Distinguishing maps, Electron. J. Combin. 18(1) (2011), #P50.
J. Tymoczko, Distinguishing numbers for graphs and groups, Electron. J. Combin. 11(1) (2004), #R63.
Refbacks
- There are currently no refbacks.
ISSN: 2338-2287
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.