{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,27]],"date-time":"2026-03-27T16:44:35Z","timestamp":1774629875135,"version":"3.50.1"},"reference-count":34,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2022,12,26]],"date-time":"2022-12-26T00:00:00Z","timestamp":1672012800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,12,26]],"date-time":"2022-12-26T00:00:00Z","timestamp":1672012800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100004281","name":"Narodowe Centrum Nauki","doi-asserted-by":"publisher","award":["2020\/37\/B\/ST1\/03298"],"award-info":[{"award-number":["2020\/37\/B\/ST1\/03298"]}],"id":[{"id":"10.13039\/501100004281","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Faculty of Applied Mathematics AGH UST"},{"DOI":"10.13039\/501100004329","name":"Javna Agencija za Raziskovalno Dejavnost RS","doi-asserted-by":"publisher","award":["J1-1693"],"award-info":[{"award-number":["J1-1693"]}],"id":[{"id":"10.13039\/501100004329","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004329","name":"Javna Agencija za Raziskovalno Dejavnost RS","doi-asserted-by":"publisher","award":["J1-9109"],"award-info":[{"award-number":["J1-9109"]}],"id":[{"id":"10.13039\/501100004329","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Comp. Appl. Math."],"published-print":{"date-parts":[[2023,2]]},"abstract":"Abstract<\/jats:title>Let G<\/jats:italic> be a graph. We introduce the acyclic b-chromatic number of G<\/jats:italic> as an analogue to the b-chromatic number of G<\/jats:italic>. An acyclic coloring of a graph G<\/jats:italic> is a map $$c:V(G)\\rightarrow \\{1,\\ldots ,k\\}$$<\/jats:tex-math>\n \n c<\/mml:mi>\n :<\/mml:mo>\n V<\/mml:mi>\n (<\/mml:mo>\n G<\/mml:mi>\n )<\/mml:mo>\n \u2192<\/mml:mo>\n {<\/mml:mo>\n 1<\/mml:mn>\n ,<\/mml:mo>\n \u2026<\/mml:mo>\n ,<\/mml:mo>\n k<\/mml:mi>\n }<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> such that $$c(u)\\ne c(v)$$<\/jats:tex-math>\n \n c<\/mml:mi>\n (<\/mml:mo>\n u<\/mml:mi>\n )<\/mml:mo>\n \u2260<\/mml:mo>\n c<\/mml:mi>\n (<\/mml:mo>\n v<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> for any $$uv\\in E(G)$$<\/jats:tex-math>\n \n u<\/mml:mi>\n v<\/mml:mi>\n \u2208<\/mml:mo>\n E<\/mml:mi>\n (<\/mml:mo>\n G<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> and the induced subgraph on vertices of any two colors $$i,j\\in \\{1,\\ldots ,k\\}$$<\/jats:tex-math>\n \n i<\/mml:mi>\n ,<\/mml:mo>\n j<\/mml:mi>\n \u2208<\/mml:mo>\n {<\/mml:mo>\n 1<\/mml:mn>\n ,<\/mml:mo>\n \u2026<\/mml:mo>\n ,<\/mml:mo>\n k<\/mml:mi>\n }<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> induces a forest. On the set of all acyclic colorings of G<\/jats:italic> we define a relation whose transitive closure is a strict partial order. The minimum cardinality of its minimal element is then the acyclic chromatic number A<\/jats:italic>(G<\/jats:italic>) of G<\/jats:italic> and the maximum cardinality of its minimal element is the acyclic b-chromatic number $$A_{\\textrm{b}}(G)$$<\/jats:tex-math>\n \n \n A<\/mml:mi>\n b<\/mml:mtext>\n <\/mml:msub>\n \n (<\/mml:mo>\n G<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> of G<\/jats:italic>. We present several properties of $$A_{\\textrm{b}}(G).$$<\/jats:tex-math>\n \n \n A<\/mml:mi>\n b<\/mml:mtext>\n <\/mml:msub>\n \n (<\/mml:mo>\n G<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n .<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> In particular, we derive $$A_{\\textrm{b}}(G)$$<\/jats:tex-math>\n \n \n A<\/mml:mi>\n b<\/mml:mtext>\n <\/mml:msub>\n \n (<\/mml:mo>\n G<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> for several known graph families, derive some bounds for $$A_{\\textrm{b}}(G),$$<\/jats:tex-math>\n \n \n A<\/mml:mi>\n b<\/mml:mtext>\n <\/mml:msub>\n \n (<\/mml:mo>\n G<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n ,<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> compare $$A_{\\textrm{b}}(G)$$<\/jats:tex-math>\n \n \n A<\/mml:mi>\n b<\/mml:mtext>\n <\/mml:msub>\n \n (<\/mml:mo>\n G<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> with some other parameters and generalize some influential tools from b-colorings to acyclic b-colorings.<\/jats:p>","DOI":"10.1007\/s40314-022-02156-y","type":"journal-article","created":{"date-parts":[[2022,12,26]],"date-time":"2022-12-26T07:02:41Z","timestamp":1672038161000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["On b-acyclic chromatic number of a graph"],"prefix":"10.1007","volume":"42","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-7322-7095","authenticated-orcid":false,"given":"Marcin","family":"Anholcer","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sylwia","family":"Cichacz","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Iztok","family":"Peterin","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2022,12,26]]},"reference":[{"issue":"3","key":"2156_CR1","doi-asserted-by":"publisher","first-page":"277","DOI":"10.1002\/rsa.3240020303","volume":"2","author":"N Alon","year":"1991","unstructured":"Alon N, McDiarmid C, Reed B (1991) Acyclic coloring of graphs. Random Struct Algorithms 2(3):277\u2013288","journal-title":"Random Struct Algorithms"},{"key":"2156_CR2","doi-asserted-by":"publisher","first-page":"273","DOI":"10.1007\/BF02762708","volume":"94","author":"N Alon","year":"1996","unstructured":"Alon N, Mohar B, Sanders DP (1996) On acyclic colorings of graphs on surfaces. Isr J Math 94:273\u2013283","journal-title":"Isr J Math"},{"key":"2156_CR3","doi-asserted-by":"publisher","first-page":"131","DOI":"10.1007\/s00037-003-0179-6","volume":"12","author":"A Bley","year":"2003","unstructured":"Bley A (2003) On the complexity of vertex-disjoint length-restricted path problems. Comput Complex 12:131\u2013149","journal-title":"Comput Complex"},{"key":"2156_CR4","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1016\/j.dam.2017.12.022","volume":"243","author":"E Bonnet","year":"2018","unstructured":"Bonnet E, Foucaud F, Kim EJ, Sikora F (2018) Complexity of Grundy coloring and its variants. Discret Appl Math 243:99\u2013114","journal-title":"Discret Appl Math"},{"key":"2156_CR5","doi-asserted-by":"publisher","first-page":"211","DOI":"10.1016\/0012-365X(79)90077-3","volume":"25","author":"OV Borodin","year":"1979","unstructured":"Borodin OV (1979) On acyclic colorings of planar graphs. Discret Math 25:211\u2013236","journal-title":"Discret Math"},{"key":"2156_CR6","doi-asserted-by":"publisher","first-page":"281","DOI":"10.1016\/j.endm.2009.11.046","volume":"35","author":"V Campos","year":"2009","unstructured":"Campos V, Linhares-Sales C, Maffray F, Silva A (2009) b-Chromatic number of cacti. Electron Notes Discret Math 35:281\u2013286","journal-title":"Electron Notes Discret Math"},{"key":"2156_CR7","doi-asserted-by":"publisher","first-page":"375","DOI":"10.1007\/s13173-012-0063-9","volume":"18","author":"V Campos","year":"2012","unstructured":"Campos V, de Farias VAE, Silva A (2012) b-Coloring graphs with large girth. J Braz Comput Soc 18:375\u2013378","journal-title":"J Braz Comput Soc"},{"key":"2156_CR8","doi-asserted-by":"publisher","first-page":"154","DOI":"10.1016\/j.ejc.2015.02.017","volume":"48","author":"V Campos","year":"2015","unstructured":"Campos V, Lima C, Silva A (2015) Graphs of girth 7 have high b-chromatic number. Eur J Combin 48:154\u2013164","journal-title":"Eur J Combin"},{"key":"2156_CR9","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1016\/0095-8956(79)90067-4","volume":"27","author":"CA Christen","year":"1979","unstructured":"Christen CA, Selkow SM (1979) Some perfect coloring properties of graphs. J Comb Theory Ser B 27:49\u201359","journal-title":"J Comb Theory Ser B"},{"key":"2156_CR10","first-page":"45","volume":"84","author":"M DeVilbiss","year":"2018","unstructured":"DeVilbiss M, Johnson P, Matzke R (2018) Edge Grundy numbers of the regular Tur\u00e1n graphs. Bull ICA 84:45\u201352","journal-title":"Bull ICA"},{"issue":"2","key":"2156_CR11","doi-asserted-by":"publisher","first-page":"157","DOI":"10.1002\/jgt.3190110205","volume":"11","author":"P Erd\u00f6s","year":"1987","unstructured":"Erd\u00f6s P, Hare WR, Hedetniemi ST, Laskar R (1987) On the equality of the Grundy and chromatic numbers of a graph. J Graph Theory 11(2):157\u2013159","journal-title":"J Graph Theory"},{"issue":"4","key":"2156_CR12","doi-asserted-by":"publisher","first-page":"507","DOI":"10.1137\/0204043","volume":"4","author":"S Even","year":"1975","unstructured":"Even S, Tarjan RE (1975) Network flow and testing graph connectivity. SIAM J Comput 4(4):507\u2013518","journal-title":"SIAM J Comput"},{"key":"2156_CR13","doi-asserted-by":"publisher","first-page":"433","DOI":"10.1007\/s10107-017-1199-3","volume":"171","author":"K Fleszar","year":"2018","unstructured":"Fleszar K, Mnich M, Spoerhase J (2018) New algorithms for maximum disjoint paths based on tree-likeness. Math Program 171:433\u2013461","journal-title":"Math Program"},{"key":"2156_CR14","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1016\/j.ipl.2007.08.022","volume":"105","author":"G Frtin","year":"2008","unstructured":"Frtin G, Raspaud A (2008) Acyclic coloring of graphs of maximum degree five: nine colors are enough. Inf Process Lett 105:65\u201372","journal-title":"Inf Process Lett"},{"key":"2156_CR15","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2019.111772","volume":"343","author":"D Gon\u00e7alves","year":"2020","unstructured":"Gon\u00e7alves D, Montassier M, Pinlou A (2020) Acyclic coloring of graphs and entropy compression method. Discret Math 343:111772","journal-title":"Discret Math"},{"key":"2156_CR16","doi-asserted-by":"crossref","unstructured":"Grossi R, Marino A, Versari L (2018) Efficient algorithms for listing $$k$$ disjoint $$st$$-paths in graphs. In: Bender M, Farach-Colton M, Mosteiro M (eds) LATIN 2018: Theoretical Informatics. LATIN 2018. Lecture Notes in Computer Science, vol 10807. Springer, Cham, pp 544\u2013557","DOI":"10.1007\/978-3-319-77404-6_40"},{"issue":"4","key":"2156_CR17","doi-asserted-by":"publisher","first-page":"390","DOI":"10.1007\/BF02764716","volume":"14","author":"B Gr\u00fcnbaum","year":"1973","unstructured":"Gr\u00fcnbaum B (1973) Acyclic colorings of planar graphs. Isr J Math 14(4):390\u2013408","journal-title":"Isr J Math"},{"key":"2156_CR18","unstructured":"Hocquard H, Montassier M (2010) Acyclic coloring of graphs with maximum degree five. hal-00375166"},{"key":"2156_CR19","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1016\/S0166-218X(98)00146-2","volume":"91","author":"RW Irving","year":"1999","unstructured":"Irving RW, Manlove DF (1999) The b-chromatic number of a graph. Discret Appl Math 91:127\u2013141","journal-title":"Discret Appl Math"},{"issue":"3","key":"2156_CR20","doi-asserted-by":"publisher","first-page":"277","DOI":"10.1002\/net.3230120306","volume":"12","author":"A Itai","year":"1982","unstructured":"Itai A, Perl Y, Shiloach Y (1982) The complexity of finding maximum disjoint paths with length constraints. Networks 12(3):277\u2013286","journal-title":"Networks"},{"key":"2156_CR21","doi-asserted-by":"publisher","first-page":"184","DOI":"10.1016\/j.dam.2017.08.008","volume":"235","author":"M Jakovac","year":"2018","unstructured":"Jakovac M, Peterin I (2018) The b-chromatic number and related topics\u2014a survey. Discret Appl Math 235:184\u2013201","journal-title":"Discret Appl Math"},{"key":"2156_CR22","volume-title":"Graph coloring problems","author":"TR Jensen","year":"1995","unstructured":"Jensen TR, Toft B (1995) Graph coloring problems. Wiley, New York"},{"key":"2156_CR23","doi-asserted-by":"publisher","first-page":"202","DOI":"10.1007\/s10878-015-9946-y","volume":"33","author":"M Kouider","year":"2017","unstructured":"Kouider M, Zamime M (2017) On the b-coloring of tight graphs. J Comb Optim 33:202\u2013214","journal-title":"J Comb Optim"},{"key":"2156_CR24","doi-asserted-by":"publisher","first-page":"310","DOI":"10.1007\/3-540-36379-3_27","volume":"2573","author":"J Kratochv\u00edl","year":"2002","unstructured":"Kratochv\u00edl J, Tuza Z, Voigt M (2002) On the b-chromatic number of graphs. Lect Notes Comput Sci 2573:310\u2013320","journal-title":"Lect Notes Comput Sci"},{"key":"2156_CR25","doi-asserted-by":"publisher","first-page":"1796","DOI":"10.1016\/j.disc.2012.01.035","volume":"312","author":"F Maffray","year":"2012","unstructured":"Maffray F, Silva A (2012) $$b$$-colouring outerplanar graphs with large girth. Discret Math 312:1796\u20131803","journal-title":"Discret Math"},{"key":"2156_CR26","doi-asserted-by":"publisher","first-page":"605","DOI":"10.1007\/s00373-020-02268-4","volume":"37","author":"Z Masih","year":"2021","unstructured":"Masih Z, Zaker M (2021) On Grundy and b-chromatic number of some families of graphs: a comparative study. Graphs Comb 37:605\u2013620","journal-title":"Graphs Comb"},{"key":"2156_CR27","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.dam.2021.09.015","volume":"306","author":"Z Masih","year":"2022","unstructured":"Masih Z, Zaker M (2022) Some comparative results concerning the Grundy and b-chromatic number of graphs. Discret Appl Math 306:1\u20136","journal-title":"Discret Appl Math"},{"key":"2156_CR28","doi-asserted-by":"publisher","first-page":"96","DOI":"10.4064\/fm-10-1-96-115","volume":"10","author":"K Menger","year":"1927","unstructured":"Menger K (1927) Zur allgemeinen Kurventheorie. Fundamenta Mathematicae 10:96\u2013115","journal-title":"Fundamenta Mathematicae"},{"key":"2156_CR29","doi-asserted-by":"publisher","first-page":"90","DOI":"10.1016\/j.jda.2012.06.001","volume":"16","author":"D Mondal","year":"2012","unstructured":"Mondal D, Nishat RI, Whitesides S, Rahman MS (2012) Acyclic colorings of graph subdivisions revisited. J Discret Algorithms 16:90\u2013103","journal-title":"J Discret Algorithms"},{"key":"2156_CR30","doi-asserted-by":"publisher","first-page":"146","DOI":"10.1007\/s00453-019-00608-2","volume":"82","author":"JE Prei\u00dfer","year":"2020","unstructured":"Prei\u00dfer JE, Schmidt JM (2020) Computing vertex-disjoint paths in large graphs using MAOs. Algorithmica 82:146\u2013162","journal-title":"Algorithmica"},{"issue":"4","key":"2156_CR31","doi-asserted-by":"publisher","first-page":"529","DOI":"10.1137\/S0895480194275825","volume":"10","author":"JA Telle","year":"1997","unstructured":"Telle JA, Proskurowski A (1997) Algorithms for vertex partitioning problems on partial $$k$$-trees. SIAM J Discret Math 10(4):529\u2013550","journal-title":"SIAM J Discret Math"},{"key":"2156_CR32","doi-asserted-by":"crossref","unstructured":"Tuite J, Thomas EJ, Chandran SV U (2022) On some extremal position problems for graphs. arXiv:2106.06827v3 [math.CO]","DOI":"10.26493\/1855-3974.3094.bc6"},{"key":"2156_CR33","doi-asserted-by":"publisher","first-page":"342","DOI":"10.1016\/j.disc.2010.10.024","volume":"311","author":"K Yadav","year":"2011","unstructured":"Yadav K, Varagani S, Kothapalli K, Venkaiah VCh (2011) Acyclic vertex coloring of graphs of maximum degree 5. Discret Math 311:342\u2013348","journal-title":"Discret Math"},{"key":"2156_CR34","doi-asserted-by":"publisher","first-page":"3166","DOI":"10.1016\/j.disc.2005.06.044","volume":"306","author":"M Zaker","year":"2006","unstructured":"Zaker M (2006) Results on the Grundy chromatic number of graphs. Discret Math 306:3166\u20133173","journal-title":"Discret Math"}],"container-title":["Computational and Applied Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s40314-022-02156-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s40314-022-02156-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s40314-022-02156-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T12:01:11Z","timestamp":1725624071000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s40314-022-02156-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,12,26]]},"references-count":34,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2023,2]]}},"alternative-id":["2156"],"URL":"https:\/\/doi.org\/10.1007\/s40314-022-02156-y","relation":{},"ISSN":["2238-3603","1807-0302"],"issn-type":[{"value":"2238-3603","type":"print"},{"value":"1807-0302","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,12,26]]},"assertion":[{"value":"14 July 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"6 December 2022","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"7 December 2022","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"26 December 2022","order":4,"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 are not aware of any competing financial or non-financial interests directly or indirectly related to this work.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}],"article-number":"21"}}