{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,11]],"date-time":"2025-09-11T19:21:49Z","timestamp":1757618509718,"version":"3.44.0"},"reference-count":19,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2025,7,2]],"date-time":"2025-07-02T00:00:00Z","timestamp":1751414400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2025,7,2]],"date-time":"2025-07-02T00:00:00Z","timestamp":1751414400000},"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"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Graphs and Combinatorics"],"published-print":{"date-parts":[[2025,8]]},"abstract":"Abstract<\/jats:title>\n An edge coloring of a graph G<\/jats:italic> is woody<\/jats:italic> if no cycle in G<\/jats:italic> is monochromatic. The arboricity<\/jats:italic> of a graph G<\/jats:italic>, denoted by \n \n $${{\\,\\textrm{arb}\\,}}(G)$$<\/jats:tex-math>\n \n \n \n \n arb<\/mml:mtext>\n \n <\/mml:mrow>\n (<\/mml:mo>\n G<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>, is defined as the least number of colors needed for a woody coloring of G<\/jats:italic>. Motivated by some recent higher-order generalizations of this parameter, we introduce here a new variant of arboricity based on the classical Whitney\u2019s idea of broken circuits. A broken cycle<\/jats:italic> in a graph G<\/jats:italic> is any simple path in G<\/jats:italic> obtained by deleting a single edge from a cycle in G<\/jats:italic>. An edge coloring of G<\/jats:italic> is strongly woody<\/jats:italic> if no broken cycle in G<\/jats:italic> is monochromatic. The least number of colors in a strongly woody coloring of G<\/jats:italic> is denoted by \n \n $$\\zeta (G)$$<\/jats:tex-math>\n \n \n \u03b6<\/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 called the strong arboricity<\/jats:italic> of G<\/jats:italic>. We prove that \n \n $$\\zeta (G)\\leqslant \\chi _a(G)$$<\/jats:tex-math>\n \n \n \u03b6<\/mml:mi>\n \n (<\/mml:mo>\n G<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n \u2a7d<\/mml:mo>\n \n \u03c7<\/mml:mi>\n a<\/mml:mi>\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>, where \n \n $$\\chi _a(G)$$<\/jats:tex-math>\n \n \n \n \u03c7<\/mml:mi>\n a<\/mml:mi>\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> is the acyclic chromatic number<\/jats:italic> of G<\/jats:italic>, defined as the least number of colors in a proper vertex coloring avoiding a 2-colored cycle. This implies that \n \n $$\\zeta (G)\\leqslant 5$$<\/jats:tex-math>\n \n \n \u03b6<\/mml:mi>\n (<\/mml:mo>\n G<\/mml:mi>\n )<\/mml:mo>\n \u2a7d<\/mml:mo>\n 5<\/mml:mn>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>, for any planar graph G<\/jats:italic>, and \n \n $$\\zeta (G)\\leqslant 3$$<\/jats:tex-math>\n \n \n \u03b6<\/mml:mi>\n (<\/mml:mo>\n G<\/mml:mi>\n )<\/mml:mo>\n \u2a7d<\/mml:mo>\n 3<\/mml:mn>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>, for any outerplanar graph. We conjecture that \n \n $$\\zeta (G)\\leqslant 4$$<\/jats:tex-math>\n \n \n \u03b6<\/mml:mi>\n (<\/mml:mo>\n G<\/mml:mi>\n )<\/mml:mo>\n \u2a7d<\/mml:mo>\n 4<\/mml:mn>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula> holds for all planar graphs and confirm this bound in the case of triangle-free planar graphs. We also prove that planar graphs with girth at least 13 satisfy \n \n $$\\zeta (G)\\leqslant 2$$<\/jats:tex-math>\n \n \n \u03b6<\/mml:mi>\n (<\/mml:mo>\n G<\/mml:mi>\n )<\/mml:mo>\n \u2a7d<\/mml:mo>\n 2<\/mml:mn>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>. In general, \n \n $$\\zeta (G)\\leqslant 4({{\\,\\textrm{arb}\\,}}(G))^2$$<\/jats:tex-math>\n \n \n \u03b6<\/mml:mi>\n \n (<\/mml:mo>\n G<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n \u2a7d<\/mml:mo>\n 4<\/mml:mn>\n \n \n (<\/mml:mo>\n \n \n arb<\/mml:mtext>\n \n <\/mml:mrow>\n \n (<\/mml:mo>\n G<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n )<\/mml:mo>\n <\/mml:mrow>\n 2<\/mml:mn>\n <\/mml:msup>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula> holds for an arbitrary graph G<\/jats:italic>, but we suspect that the true upper bound is linear. The paper is concluded with some open problems.<\/jats:p>","DOI":"10.1007\/s00373-025-02934-5","type":"journal-article","created":{"date-parts":[[2025,7,2]],"date-time":"2025-07-02T15:49:57Z","timestamp":1751471397000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Strong Arboricity of Graphs"],"prefix":"10.1007","volume":"41","author":[{"given":"Tomasz","family":"Bartnicki","sequence":"first","affiliation":[]},{"given":"Sebastian","family":"Czerwi\u0144ski","sequence":"additional","affiliation":[]},{"given":"Jaros\u0142aw","family":"Grytczuk","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2967-129X","authenticated-orcid":false,"given":"Zofia","family":"Miechowicz","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2025,7,2]]},"reference":[{"key":"2934_CR1","doi-asserted-by":"publisher","DOI":"10.37236\/1779","volume":"11","author":"MO Albertson","year":"2004","unstructured":"Albertson, M.O., Chappell, G.G., Kierstead, H.A., K\u00fcndgen, A., Ramamurthi, R.: Coloring with no 2-colored. Electron. J. Comb. 11, 26 (2004)","journal-title":"Electron. J. Comb."},{"key":"2934_CR2","doi-asserted-by":"publisher","first-page":"231","DOI":"10.1016\/S0095-8956(02)00006-0","volume":"87","author":"N Alon","year":"2003","unstructured":"Alon, N., Ding, G., Oporowski, B., Vertigan, D.: Partitioning into graphs with only small components. J. Combin. Theory Ser. B 87, 231\u2013243 (2003)","journal-title":"J. Combin. Theory Ser. B"},{"key":"2934_CR3","doi-asserted-by":"publisher","DOI":"10.1002\/0471722154","volume-title":"The Probabilistic Method","author":"N Alon","year":"2000","unstructured":"Alon, N., Spencer, J.H.: The Probabilistic Method. Wiley, New York (2000)"},{"key":"2934_CR4","doi-asserted-by":"publisher","first-page":"157","DOI":"10.1002\/jgt.1010","volume":"37","author":"N Alon","year":"2001","unstructured":"Alon, N., Sudakov, B., Zaks, A.: Acyclic edge colorings of graphs. J. Graph Theory 37, 157\u2013167 (2001)","journal-title":"J. Graph Theory"},{"key":"2934_CR5","doi-asserted-by":"publisher","first-page":"1343","DOI":"10.1016\/j.disc.2019.01.018","volume":"342","author":"T Bartnicki","year":"2019","unstructured":"Bartnicki, T., Bosek, B., Czerwi\u0144ski, S., Farnik, M., Grytczuk, J., Miechowicz, Z.: Generalized arboricity of graphs with large girth. Discrete Math. 342, 1343\u20131350 (2019)","journal-title":"Discrete Math."},{"key":"2934_CR6","volume-title":"Algebraic Graph Theory","author":"N Biggs","year":"1994","unstructured":"Biggs, N.: Algebraic Graph Theory, 2nd edn. Cambridge University Press, Cambridge (1994)","edition":"2"},{"key":"2934_CR7","doi-asserted-by":"publisher","first-page":"211","DOI":"10.1016\/0012-365X(79)90077-3","volume":"25","author":"OV Borodin","year":"1979","unstructured":"Borodin, O.V.: On acyclic colorings of planar graphs. Discrete Math. 25, 211\u2013236 (1979)","journal-title":"Discrete Math."},{"key":"2934_CR8","doi-asserted-by":"publisher","first-page":"201","DOI":"10.1002\/jgt.20392","volume":"62","author":"Y Bu","year":"2009","unstructured":"Bu, Y., Cranston, D.W., Montassier, M., Raspaud, A., Wang, W.: Star coloring of sparse graphs. J. Graph Theory 62, 201\u2013219 (2009)","journal-title":"J. Graph Theory"},{"key":"2934_CR9","doi-asserted-by":"publisher","first-page":"2691","DOI":"10.1016\/j.disc.2016.07.026","volume":"340","author":"J Czap","year":"2017","unstructured":"Czap, J., Jendrol\u2019, S.: Facially-constrained colorings of plane graphs: A survey. Discrete Math. 340, 2691\u20132703 (2017)","journal-title":"Discrete Math."},{"key":"2934_CR10","doi-asserted-by":"publisher","first-page":"80","DOI":"10.1016\/j.dam.2019.11.003","volume":"282","author":"J Czap","year":"2020","unstructured":"Czap, J., Jendrol\u2019, S., Valiska, J.: Edge-coloring of plane multigraphs with many colors on facial cycles. Discrete Appl. Math. 282, 80\u201385 (2020)","journal-title":"Discrete Appl. Math."},{"key":"2934_CR11","doi-asserted-by":"publisher","first-page":"509","DOI":"10.7151\/dmgt.1561","volume":"31","author":"K Dohmen","year":"2011","unstructured":"Dohmen, K.: An inductive proof of Whitney\u2019s Broken Circuit Theorem. Dicuss. Math. Graph Theory 31, 509\u2013515 (2011)","journal-title":"Dicuss. Math. Graph Theory"},{"issue":"2","key":"2934_CR12","first-page":"139","volume":"28","author":"J Fiam\u010dik","year":"1978","unstructured":"Fiam\u010dik, J.: The acyclic chromatic class of a graph. Math. Slovaca 28(2), 139\u2013145 (1978). (in Russian)","journal-title":"Math. Slovaca"},{"key":"2934_CR13","doi-asserted-by":"publisher","first-page":"407","DOI":"10.1007\/s00373-005-0635-y","volume":"21","author":"C Greenhill","year":"2005","unstructured":"Greenhill, C., Pikhurko, O.: Bounds on generalised acyclic chromatic numbers for bounded degree graphs. Graphs Combin. 21, 407\u2013419 (2005)","journal-title":"Graphs Combin."},{"key":"2934_CR14","doi-asserted-by":"publisher","first-page":"445","DOI":"10.1112\/jlms\/s1-36.1.445","volume":"36","author":"CSJA Nash-Williams","year":"1961","unstructured":"Nash-Williams, C.S.J.A.: Edge-disjoint spanning trees of finite graphs. J. Lond. Math. Soc. 36, 445\u2013450 (1961)","journal-title":"J. Lond. Math. Soc."},{"key":"2934_CR15","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-27875-4","volume-title":"Sparsity","author":"J Ne\u0161et\u0159il","year":"2012","unstructured":"Ne\u0161et\u0159il, J., Ossona de Mendez, P.: Sparsity. Springer, Berlin (2012)"},{"key":"2934_CR16","doi-asserted-by":"publisher","first-page":"102","DOI":"10.1016\/j.jctb.2014.06.002","volume":"109","author":"J Ne\u0161et\u0159il","year":"2014","unstructured":"Ne\u0161et\u0159il, J., Ossona de Mendez, P., Zhu, X.: Colouring edges with many colours in cycles. J. Combin. Theory Ser. B 109, 102\u2013119 (2014)","journal-title":"J. Combin. Theory Ser. B"},{"key":"2934_CR17","first-page":"97","volume-title":"Selected Topics in Graph Theory","author":"C Thomassen","year":"1988","unstructured":"Thomassen, C.: Paths, circuits and subdivisions. In: Selected Topics in Graph Theory, vol. 3, pp. 97\u2013131. Academic Press, New York (1988)"},{"issue":"1","key":"2934_CR18","doi-asserted-by":"publisher","first-page":"100","DOI":"10.1006\/jctb.1998.1868","volume":"75","author":"C Thomassen","year":"1999","unstructured":"Thomassen, C.: Two-coloring the edges of a cubic graph such that each monochromatic component is a path of length at most 5. J. Combin. Theory Series B 75(1), 100\u2013109 (1999)","journal-title":"J. Combin. Theory Series B"},{"key":"2934_CR19","doi-asserted-by":"publisher","first-page":"572","DOI":"10.1090\/S0002-9904-1932-05460-X","volume":"38","author":"H Whitney","year":"1932","unstructured":"Whitney, H.: A logical expansion in mathematics. Bull. Am. Math. Soc. 38, 572\u2013579 (1932)","journal-title":"Bull. Am. Math. Soc."}],"container-title":["Graphs and Combinatorics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00373-025-02934-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00373-025-02934-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00373-025-02934-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,9,7]],"date-time":"2025-09-07T00:41:27Z","timestamp":1757205687000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00373-025-02934-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,7,2]]},"references-count":19,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2025,8]]}},"alternative-id":["2934"],"URL":"https:\/\/doi.org\/10.1007\/s00373-025-02934-5","relation":{},"ISSN":["0911-0119","1435-5914"],"issn-type":[{"type":"print","value":"0911-0119"},{"type":"electronic","value":"1435-5914"}],"subject":[],"published":{"date-parts":[[2025,7,2]]},"assertion":[{"value":"12 December 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"14 May 2025","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"2 July 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 have not disclosed any competing interests.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}],"article-number":"80"}}