{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,2]],"date-time":"2025-06-02T09:40:04Z","timestamp":1748857204637,"version":"3.41.0"},"reference-count":15,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2025,4,16]],"date-time":"2025-04-16T00:00:00Z","timestamp":1744761600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2025,4,16]],"date-time":"2025-04-16T00:00:00Z","timestamp":1744761600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Graphs and Combinatorics"],"published-print":{"date-parts":[[2025,6]]},"abstract":"Abstract<\/jats:title>\n In this paper, all results apply only to finite graphs. Let G<\/jats:italic> be a simple connected finite graph with n<\/jats:italic> vertices and maximum degree \n \n $$\\Delta (G)$$<\/jats:tex-math>\n \n \n \u0394<\/mml:mi>\n (<\/mml:mo>\n G<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>. We show that the list-distinguishing chromatic number \n \n $$\\chi _{D_{L}}(G)$$<\/jats:tex-math>\n \n \n \n \u03c7<\/mml:mi>\n \n D<\/mml:mi>\n L<\/mml:mi>\n <\/mml:msub>\n <\/mml:msub>\n \n (<\/mml:mo>\n G<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula> of G<\/jats:italic> is at most \n \n $$2\\Delta (G)$$<\/jats:tex-math>\n \n \n 2<\/mml:mn>\n \u0394<\/mml:mi>\n (<\/mml:mo>\n G<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>, and it is \n \n $$2\\Delta (G)$$<\/jats:tex-math>\n \n \n 2<\/mml:mn>\n \u0394<\/mml:mi>\n (<\/mml:mo>\n G<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula> if G<\/jats:italic> is a complete bipartite graph \n \n $$K_{\\Delta (G),\\Delta (G)}$$<\/jats:tex-math>\n \n \n K<\/mml:mi>\n \n \u0394<\/mml:mi>\n (<\/mml:mo>\n G<\/mml:mi>\n )<\/mml:mo>\n ,<\/mml:mo>\n \u0394<\/mml:mi>\n (<\/mml:mo>\n G<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:msub>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula> or a cycle with six vertices. We apply a result of Lov\u00e1sz to reduce the above-mentioned upper bound of \n \n $$\\chi _{D_{L}}(G)$$<\/jats:tex-math>\n \n \n \n \u03c7<\/mml:mi>\n \n D<\/mml:mi>\n L<\/mml:mi>\n <\/mml:msub>\n <\/mml:msub>\n \n (<\/mml:mo>\n G<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula> for certain graphs. We also show that if H<\/jats:italic> is a connected unicyclic graph of girth of at least seven and \n \n $$\\Delta (H)\\ge 3$$<\/jats:tex-math>\n \n \n \u0394<\/mml:mi>\n (<\/mml:mo>\n H<\/mml:mi>\n )<\/mml:mo>\n \u2265<\/mml:mo>\n 3<\/mml:mn>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>, then \n \n $$\\chi _{D_{L}}(H)$$<\/jats:tex-math>\n \n \n \n \u03c7<\/mml:mi>\n \n D<\/mml:mi>\n L<\/mml:mi>\n <\/mml:msub>\n <\/mml:msub>\n \n (<\/mml:mo>\n H<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula> is at most \n \n $$\\Delta (H)$$<\/jats:tex-math>\n \n \n \u0394<\/mml:mi>\n (<\/mml:mo>\n H<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>. Moreover, we obtain two upper bounds for \n \n $$\\chi _{D_{L}}(G)$$<\/jats:tex-math>\n \n \n \n \u03c7<\/mml:mi>\n \n D<\/mml:mi>\n L<\/mml:mi>\n <\/mml:msub>\n <\/mml:msub>\n \n (<\/mml:mo>\n G<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula> in terms of the coloring number of G<\/jats:italic> and the list chromatic number of G<\/jats:italic>. We also determine the list-distinguishing chromatic number for some special graphs.<\/jats:p>","DOI":"10.1007\/s00373-025-02920-x","type":"journal-article","created":{"date-parts":[[2025,4,16]],"date-time":"2025-04-16T13:59:38Z","timestamp":1744811978000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Upper Bounds for the List-Distinguishing Chromatic Number"],"prefix":"10.1007","volume":"41","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-4156-7209","authenticated-orcid":false,"given":"Amitayu","family":"Banerjee","sequence":"first","affiliation":[]},{"given":"Zal\u00e1n","family":"Moln\u00e1r","sequence":"additional","affiliation":[]},{"given":"Alexa","family":"Gopaulsingh","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2025,4,16]]},"reference":[{"key":"2920_CR1","doi-asserted-by":"publisher","first-page":"9","DOI":"10.37236\/1242","volume":"3","author":"MO Albertson","year":"1996","unstructured":"Albertson, M.O., Collins, K.L.: Symmetry breaking in graphs. Electron. J. Combin. 3, 9 (1996)","journal-title":"Electron. J. Combin."},{"key":"2920_CR2","first-page":"81","volume":"3","author":"S Alikhani","year":"2016","unstructured":"Alikhani, S., Soltani, S.: The distinguishing chromatic number of bipartite graphs of girth at least six. Algebr. struct. appl. 3, 81\u201387 (2016)","journal-title":"Algebr. struct. appl."},{"issue":"14","key":"2920_CR3","doi-asserted-by":"publisher","first-page":"4393","DOI":"10.2298\/FIL1714393A","volume":"31","author":"S Alikhani","year":"2017","unstructured":"Alikhani, S., Soltani, S.: Distinguishing number and distinguishing index of certain graphs. Filomat 31(14), 4393\u20134404 (2017)","journal-title":"Filomat"},{"key":"2920_CR4","unstructured":"Alikhani, S., Soltani, S.: Characterization of graphs with distinguishing number equal list-distinguishing number, arXiv preprint arXiv:1711.08887"},{"key":"2920_CR5","doi-asserted-by":"publisher","first-page":"247","DOI":"10.1016\/0095-8956(77)90037-5","volume":"23","author":"OV Borodin","year":"1977","unstructured":"Borodin, O.V., Kostochka, A.V.: On an upper bound of a graph\u2019s chromatic number, depending on the graph\u2019s degree and density. J. Combin Theory B 23, 247\u2013250 (1977)","journal-title":"J. Combin Theory B"},{"key":"2920_CR6","doi-asserted-by":"publisher","first-page":"81","DOI":"10.1016\/0012-365X(78)90049-3","volume":"22","author":"PA Catlin","year":"1978","unstructured":"Catlin, P.A.: A bound on the chromatic number of a graph. Discr. Math. 22, 81\u201383 (1978)","journal-title":"Discr. Math."},{"key":"2920_CR7","doi-asserted-by":"publisher","first-page":"9","DOI":"10.37236\/177","volume":"16","author":"KL Collins","year":"2009","unstructured":"Collins, K.L., Hovey, M., Trenk, A.N.: Bounds on the distinguishing chromatic number. Electron. J. Combin. 16, 9 (2009)","journal-title":"Electron. J. Combin."},{"key":"2920_CR8","doi-asserted-by":"publisher","first-page":"9","DOI":"10.37236\/1042","volume":"13","author":"KL Collins","year":"2006","unstructured":"Collins, K.L., Trenk, A.N.: The distinguishing chromatic number. Electron. J. Combin. 13, 9 (2006)","journal-title":"Electron. J. Combin."},{"key":"2920_CR9","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1007\/BF02020444","volume":"17","author":"P Erd\u0151s","year":"1966","unstructured":"Erd\u0151s, P., Hajnal, A.: On chromatic number of graphs and set-systems. Acta Math. Acad. Sci. Hungar. 17, 61\u201399 (1966)","journal-title":"Acta Math. Acad. Sci. Hungar."},{"key":"2920_CR10","first-page":"125","volume":"26","author":"P Erd\u0151s","year":"1979","unstructured":"Erd\u0151s, P., Rubin, A.L., Taylor, H.: Choosability in graphs. Proc. West Coast Conf. Combin. Graph Theory Comput. Congressus Numer. 26, 125\u2013157 (1979)","journal-title":"Proc. West Coast Conf. Combin. Graph Theory Comput. Congressus Numer."},{"key":"2920_CR11","doi-asserted-by":"publisher","first-page":"864","DOI":"10.1016\/j.dam.2012.10.003","volume":"161","author":"M Ferrara","year":"2013","unstructured":"Ferrara, M., Gethner, E., Hartke, S.G., Stolee, D., Wenger, P.S.: List distinguishing parameters of trees. Discr. Appl. Math. 161, 864\u2013869 (2013)","journal-title":"Discr. Appl. Math."},{"key":"2920_CR12","doi-asserted-by":"publisher","first-page":"8","DOI":"10.37236\/6362","volume":"24","author":"W Imrich","year":"2017","unstructured":"Imrich, W., Kalinowski, R., Pil\u015bniak, M., Shekarriz, M.H.: Bounds for distinguishing invariants of infinite graphs. Electron. J. Combin. 24, 8 (2017)","journal-title":"Electron. J. Combin."},{"key":"2920_CR13","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1016\/0012-365X(78)90147-4","volume":"21","author":"J Lawrence","year":"1978","unstructured":"Lawrence, J.: Covering the vertex set of a graph with subgraphs of smaller degree. Discr. Math. 21, 61\u201368 (1978)","journal-title":"Discr. Math."},{"key":"2920_CR14","first-page":"237","volume":"1","author":"L Lov\u00e1sz","year":"1966","unstructured":"Lov\u00e1sz, L.: On decomposition of graphs. Studia Math. Hung. 1, 237\u2013238 (1966)","journal-title":"Studia Math. Hung."},{"key":"2920_CR15","first-page":"3","volume":"29","author":"VG Vizing","year":"1976","unstructured":"Vizing, V.G.: Vertex coloring of a graph with assigned colors. Metody Diskret. Analiz. (Novosibirsk) 29, 3\u201310 (1976). ((in Russian))","journal-title":"Metody Diskret. Analiz. (Novosibirsk)"}],"container-title":["Graphs and Combinatorics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00373-025-02920-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00373-025-02920-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00373-025-02920-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,2]],"date-time":"2025-06-02T09:15:21Z","timestamp":1748855721000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00373-025-02920-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,4,16]]},"references-count":15,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2025,6]]}},"alternative-id":["2920"],"URL":"https:\/\/doi.org\/10.1007\/s00373-025-02920-x","relation":{},"ISSN":["0911-0119","1435-5914"],"issn-type":[{"type":"print","value":"0911-0119"},{"type":"electronic","value":"1435-5914"}],"subject":[],"published":{"date-parts":[[2025,4,16]]},"assertion":[{"value":"10 June 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"2 April 2025","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"16 April 2025","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare that they have no Conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}],"article-number":"59"}}