[{"file":[{"access_level":"open_access","date_created":"2025-06-24T06:33:30Z","file_size":564203,"success":1,"content_type":"application/pdf","file_name":"2025_EuropJournCombinatorics_Dvorak.pdf","checksum":"8b3585df45b25091fba9bee9854b7d01","date_updated":"2025-06-24T06:33:30Z","relation":"main_file","file_id":"19887","creator":"dernst"}],"publication_status":"published","oa_version":"Published Version","OA_type":"hybrid","date_created":"2025-06-23T13:54:46Z","title":"Precoloring extension in planar near-Eulerian-triangulations","publication_identifier":{"issn":["0195-6698"]},"arxiv":1,"article_type":"original","month":"06","department":[{"_id":"MaKw"}],"volume":127,"author":[{"first_name":"Zdeněk","full_name":"Dvořák, Zdeněk","last_name":"Dvořák"},{"first_name":"Benjamin","id":"6dc1a1be-bf1c-11ed-8d2b-d044840f49d6","last_name":"Moore","full_name":"Moore, Benjamin"},{"first_name":"Michaela","full_name":"Seifrtová, Michaela","last_name":"Seifrtová"},{"last_name":"Šámal","full_name":"Šámal, Robert","first_name":"Robert"}],"acknowledgement":"Supported by project 22-17398S (Flows and cycles in graphs on surfaces) of Czech Science Foundation. An extended abstract appeared in Proceedings of the 12th European Conference on Combinatorics, Graph Theory and Applications (EUROCOMB’23)","doi":"10.1016/j.ejc.2025.104138","oa":1,"publisher":"Elsevier","tmp":{"short":"CC BY (4.0)","image":"/images/cc_by.png","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)"},"corr_author":"1","article_processing_charge":"Yes (via OA deal)","has_accepted_license":"1","citation":{"ama":"Dvořák Z, Moore B, Seifrtová M, Šámal R. Precoloring extension in planar near-Eulerian-triangulations. <i>European Journal of Combinatorics</i>. 2025;127. doi:<a href=\"https://doi.org/10.1016/j.ejc.2025.104138\">10.1016/j.ejc.2025.104138</a>","ista":"Dvořák Z, Moore B, Seifrtová M, Šámal R. 2025. Precoloring extension in planar near-Eulerian-triangulations. European Journal of Combinatorics. 127, 104138.","chicago":"Dvořák, Zdeněk, Benjamin Moore, Michaela Seifrtová, and Robert Šámal. “Precoloring Extension in Planar Near-Eulerian-Triangulations.” <i>European Journal of Combinatorics</i>. Elsevier, 2025. <a href=\"https://doi.org/10.1016/j.ejc.2025.104138\">https://doi.org/10.1016/j.ejc.2025.104138</a>.","mla":"Dvořák, Zdeněk, et al. “Precoloring Extension in Planar Near-Eulerian-Triangulations.” <i>European Journal of Combinatorics</i>, vol. 127, 104138, Elsevier, 2025, doi:<a href=\"https://doi.org/10.1016/j.ejc.2025.104138\">10.1016/j.ejc.2025.104138</a>.","ieee":"Z. Dvořák, B. Moore, M. Seifrtová, and R. Šámal, “Precoloring extension in planar near-Eulerian-triangulations,” <i>European Journal of Combinatorics</i>, vol. 127. Elsevier, 2025.","short":"Z. Dvořák, B. Moore, M. Seifrtová, R. Šámal, European Journal of Combinatorics 127 (2025).","apa":"Dvořák, Z., Moore, B., Seifrtová, M., &#38; Šámal, R. (2025). Precoloring extension in planar near-Eulerian-triangulations. <i>European Journal of Combinatorics</i>. Elsevier. <a href=\"https://doi.org/10.1016/j.ejc.2025.104138\">https://doi.org/10.1016/j.ejc.2025.104138</a>"},"day":"01","type":"journal_article","quality_controlled":"1","abstract":[{"lang":"eng","text":"We consider the 4-precoloring extension problem in planar near-Eulerian- triangulations, i.e., plane graphs where all faces except possibly for the outer one have length three, all vertices not incident with the outer face have even degree, and exactly the vertices incident with the outer face are precolored. We give a necessary topological condition for the precoloring to extend, and give a complete characterization when the outer face has length at most five and when all vertices of the outer face have odd degree and are colored using only three colors."}],"_id":"19879","language":[{"iso":"eng"}],"external_id":{"arxiv":["2312.13061"],"isi":["001443061400001"]},"date_published":"2025-06-01T00:00:00Z","OA_place":"publisher","year":"2025","ddc":["510"],"user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","article_number":"104138","intvolume":"       127","isi":1,"date_updated":"2025-09-30T13:42:59Z","publication":"European Journal of Combinatorics","file_date_updated":"2025-06-24T06:33:30Z","scopus_import":"1","status":"public"},{"doi":"10.1145/3717823.3718173","oa":1,"acknowledgement":"All authors were supported by ERC Starting Grant “RANDSTRUCT” No. 101076777. Michael Anastos was also supported in part by the Austrian Science Fund (FWF)[10.55776/ESP3863424] and by the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie grant agreement No. 101034413. For Open Access purposes, the authors have applied a CC BY public copyright license to any author accepted manuscript version arising from this submission.","month":"06","department":[{"_id":"MaKw"}],"project":[{"name":"Randomness and structure in combinatorics","grant_number":"101076777","_id":"bd95085b-d553-11ed-ba76-e55d3349be45"},{"_id":"fc2ed2f7-9c52-11eb-aca3-c01059dda49c","call_identifier":"H2020","grant_number":"101034413","name":"IST-BRIDGE: International postdoctoral program"},{"name":"Combinatorial Optimisation Problems on Sparse Random Graphs","_id":"8f906bd2-16d5-11f0-9cad-e07be8aa9ac9","grant_number":"ESP3863424"}],"author":[{"id":"0b2a4358-bb35-11ec-b7b9-e3279b593dbb","first_name":"Michael","last_name":"Anastos","full_name":"Anastos, Michael"},{"first_name":"Matthew Alan","id":"5fca0887-a1db-11eb-95d1-ca9d5e0453b3","orcid":"0000-0002-4003-7567","full_name":"Kwan, Matthew Alan","last_name":"Kwan"},{"id":"6dc1a1be-bf1c-11ed-8d2b-d044840f49d6","first_name":"Benjamin","last_name":"Moore","full_name":"Moore, Benjamin"}],"publisher":"Association for Computing Machinery","article_processing_charge":"Yes (via OA deal)","corr_author":"1","tmp":{"short":"CC BY (4.0)","image":"/images/cc_by.png","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)"},"conference":{"name":"STOC: Symposium on Theory of Computing","start_date":"2025-06-23","end_date":"2025-06-27","location":"Prague, Czechia"},"publication_status":"published","file":[{"access_level":"open_access","date_created":"2025-07-14T06:13:10Z","file_size":706445,"success":1,"content_type":"application/pdf","file_name":"2025_STOC_Anastos.pdf","checksum":"cf0ab9cb9c6abda188de13dc3f9a4c9b","date_updated":"2025-07-14T06:13:10Z","creator":"dernst","file_id":"20012","relation":"main_file"}],"publication_identifier":{"isbn":["9798400715105"],"issn":["0737-8017"]},"arxiv":1,"OA_type":"hybrid","oa_version":"Published Version","title":"Smoothed analysis for graph isomorphism","date_created":"2025-07-13T22:01:23Z","file_date_updated":"2025-07-14T06:13:10Z","publication":"Proceedings of the 57th Annual ACM Symposium on Theory of Computing","date_updated":"2025-07-14T06:33:50Z","page":"2098-2106","status":"public","scopus_import":"1","ec_funded":1,"quality_controlled":"1","type":"conference","external_id":{"arxiv":["2410.06095"]},"abstract":[{"text":"There is no known polynomial-time algorithm for graph isomorphism testing, but elementary combinatorial “refinement” algorithms seem to be very efficient in practice. Some philosophical justification for this phenomenon is provided by a classical theorem of Babai, Erdős and Selkow: an extremely simple polynomial-time combinatorial algorithm (variously known as “naïve refinement”, “naïve vertex classification”, “colour refinement” or the “1-dimensional Weisfeiler–Leman algorithm”) yields a so-called canonical labelling scheme for “almost all graphs”. More precisely, for a typical outcome of a random graph G(n,1/2), this simple combinatorial algorithm assigns labels to vertices in a way that easily permits isomorphism-testing against any other graph.","lang":"eng"}],"_id":"20007","language":[{"iso":"eng"}],"day":"15","citation":{"chicago":"Anastos, Michael, Matthew Alan Kwan, and Benjamin Moore. “Smoothed Analysis for Graph Isomorphism.” In <i>Proceedings of the 57th Annual ACM Symposium on Theory of Computing</i>, 2098–2106. Association for Computing Machinery, 2025. <a href=\"https://doi.org/10.1145/3717823.3718173\">https://doi.org/10.1145/3717823.3718173</a>.","ama":"Anastos M, Kwan MA, Moore B. Smoothed analysis for graph isomorphism. In: <i>Proceedings of the 57th Annual ACM Symposium on Theory of Computing</i>. Association for Computing Machinery; 2025:2098-2106. doi:<a href=\"https://doi.org/10.1145/3717823.3718173\">10.1145/3717823.3718173</a>","ista":"Anastos M, Kwan MA, Moore B. 2025. Smoothed analysis for graph isomorphism. Proceedings of the 57th Annual ACM Symposium on Theory of Computing. STOC: Symposium on Theory of Computing, 2098–2106.","apa":"Anastos, M., Kwan, M. A., &#38; Moore, B. (2025). Smoothed analysis for graph isomorphism. In <i>Proceedings of the 57th Annual ACM Symposium on Theory of Computing</i> (pp. 2098–2106). Prague, Czechia: Association for Computing Machinery. <a href=\"https://doi.org/10.1145/3717823.3718173\">https://doi.org/10.1145/3717823.3718173</a>","mla":"Anastos, Michael, et al. “Smoothed Analysis for Graph Isomorphism.” <i>Proceedings of the 57th Annual ACM Symposium on Theory of Computing</i>, Association for Computing Machinery, 2025, pp. 2098–106, doi:<a href=\"https://doi.org/10.1145/3717823.3718173\">10.1145/3717823.3718173</a>.","short":"M. Anastos, M.A. Kwan, B. Moore, in:, Proceedings of the 57th Annual ACM Symposium on Theory of Computing, Association for Computing Machinery, 2025, pp. 2098–2106.","ieee":"M. Anastos, M. A. Kwan, and B. Moore, “Smoothed analysis for graph isomorphism,” in <i>Proceedings of the 57th Annual ACM Symposium on Theory of Computing</i>, Prague, Czechia, 2025, pp. 2098–2106."},"has_accepted_license":"1","ddc":["000"],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","year":"2025","OA_place":"publisher","date_published":"2025-06-15T00:00:00Z"},{"date_created":"2025-09-10T05:36:50Z","title":"Beyond the pseudoforest strong Nine Dragon Tree theorem","OA_type":"hybrid","oa_version":"Published Version","arxiv":1,"publication_identifier":{"issn":["0195-6698"]},"file":[{"relation":"main_file","creator":"dernst","file_id":"20913","date_updated":"2025-12-30T10:18:56Z","file_name":"2025_EuropJournCombinatorics_Mies.pdf","checksum":"b1536e9256c4510a0e21452032e43a26","date_created":"2025-12-30T10:18:56Z","file_size":737845,"content_type":"application/pdf","success":1,"access_level":"open_access"}],"publication_status":"published","article_processing_charge":"Yes (via OA deal)","tmp":{"short":"CC BY (4.0)","image":"/images/cc_by.png","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)"},"corr_author":"1","publisher":"Elsevier","volume":130,"author":[{"full_name":"Mies, Sebastian","last_name":"Mies","first_name":"Sebastian"},{"last_name":"Moore","full_name":"Moore, Benjamin","first_name":"Benjamin","id":"6dc1a1be-bf1c-11ed-8d2b-d044840f49d6"},{"full_name":"Smith-Roberge, Evelyne","last_name":"Smith-Roberge","first_name":"Evelyne"}],"department":[{"_id":"MaKw"}],"month":"12","article_type":"original","oa":1,"doi":"10.1016/j.ejc.2025.104214","acknowledgement":"This work was completed while Benjamin Moore was a postdoc at Charles University, supported by project 22-17398S (Flows and cycles in graphs on surfaces) of Czech Science Foundation, Czechia.","OA_place":"publisher","date_published":"2025-12-01T00:00:00Z","article_number":"104214","intvolume":"       130","ddc":["500"],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","year":"2025","citation":{"chicago":"Mies, Sebastian, Benjamin Moore, and Evelyne Smith-Roberge. “Beyond the Pseudoforest Strong Nine Dragon Tree Theorem.” <i>European Journal of Combinatorics</i>. Elsevier, 2025. <a href=\"https://doi.org/10.1016/j.ejc.2025.104214\">https://doi.org/10.1016/j.ejc.2025.104214</a>.","ista":"Mies S, Moore B, Smith-Roberge E. 2025. Beyond the pseudoforest strong Nine Dragon Tree theorem. European Journal of Combinatorics. 130(12), 104214.","ama":"Mies S, Moore B, Smith-Roberge E. Beyond the pseudoforest strong Nine Dragon Tree theorem. <i>European Journal of Combinatorics</i>. 2025;130(12). doi:<a href=\"https://doi.org/10.1016/j.ejc.2025.104214\">10.1016/j.ejc.2025.104214</a>","apa":"Mies, S., Moore, B., &#38; Smith-Roberge, E. (2025). Beyond the pseudoforest strong Nine Dragon Tree theorem. <i>European Journal of Combinatorics</i>. Elsevier. <a href=\"https://doi.org/10.1016/j.ejc.2025.104214\">https://doi.org/10.1016/j.ejc.2025.104214</a>","ieee":"S. Mies, B. Moore, and E. Smith-Roberge, “Beyond the pseudoforest strong Nine Dragon Tree theorem,” <i>European Journal of Combinatorics</i>, vol. 130, no. 12. Elsevier, 2025.","short":"S. Mies, B. Moore, E. Smith-Roberge, European Journal of Combinatorics 130 (2025).","mla":"Mies, Sebastian, et al. “Beyond the Pseudoforest Strong Nine Dragon Tree Theorem.” <i>European Journal of Combinatorics</i>, vol. 130, no. 12, 104214, Elsevier, 2025, doi:<a href=\"https://doi.org/10.1016/j.ejc.2025.104214\">10.1016/j.ejc.2025.104214</a>."},"day":"01","has_accepted_license":"1","external_id":{"arxiv":["2310.00931"],"isi":["001529769300002"]},"_id":"20320","abstract":[{"text":"The pseudoforest version of the Strong Nine Dragon Tree Conjecture states that if a graph G has maximum average degree mad(G) = 2 maxH⊆G e(H)/v(H) at most 2(k + d/d+k+1), then it has a decomposition into k + 1 pseudoforests where in one pseudoforest F the components of F have at most d edges. This was proven in 2020 in Grout and Moore (2020). We strengthen this\r\ntheorem by showing that we can find such a decomposition where additionally F is acyclic, the diameter of the components of F is at most 2ℓ + 2, where ℓ =⌊d−1/k+1⌋, and at most 2ℓ + 1 if\r\nd ≡ 1 mod (k + 1). Furthermore, for any component K of F and any z ∈ N, we have diam(K) ≤ 2z if e(K) ≥ d − z(k − 1) + 1. We also show that both diameter bounds are best possible as an\r\nextension for both the Strong Nine Dragon Tree Conjecture for pseudoforests and its original conjecture for forests. In fact, they are still optimal even if we only enforce F to have any constant maximum degree, instead of enforcing every component of F to have at most d edges.","lang":"eng"}],"language":[{"iso":"eng"}],"quality_controlled":"1","type":"journal_article","issue":"12","scopus_import":"1","PlanS_conform":"1","status":"public","publication":"European Journal of Combinatorics","date_updated":"2025-12-30T10:19:10Z","isi":1,"file_date_updated":"2025-12-30T10:18:56Z"},{"publisher":"Elsevier","article_processing_charge":"Yes (in subscription journal)","corr_author":"1","tmp":{"short":"CC BY (4.0)","image":"/images/cc_by.png","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)"},"month":"03","department":[{"_id":"MaKw"}],"project":[{"name":"Randomness and structure in combinatorics","grant_number":"101076777","_id":"bd95085b-d553-11ed-ba76-e55d3349be45"}],"article_type":"original","author":[{"full_name":"Carbonero, Alvaro","last_name":"Carbonero","first_name":"Alvaro"},{"full_name":"Koerts, Hidde","last_name":"Koerts","first_name":"Hidde"},{"id":"6dc1a1be-bf1c-11ed-8d2b-d044840f49d6","first_name":"Benjamin","last_name":"Moore","full_name":"Moore, Benjamin"},{"first_name":"Sophie","last_name":"Spirkl","full_name":"Spirkl, Sophie"}],"volume":125,"doi":"10.1016/j.ejc.2024.104104","oa":1,"acknowledgement":"We thank the anonymous referees for their careful proofreading which helped improve the presentation of this paper. We also thank one of the anonymous referees for pointing out our construction implies Theorem 1.7!\r\nBenjamin Moore finished this project while a postdoctoral researcher at Charles University, and was supported by project 22-17398S (Flows and cycles in graphs on surfaces) of the Czech Science Foundation. Benjamin Moore is currently funded by RANDSTRUCT No. 101076777, and appreciates the gracious support. We acknowledge the support of the Natural Sciences and Engineering Research Council of Canada (NSERC), [funding reference number RGPIN-2020-03912]. Cette recherche a été financée par le Conseil de recherches en sciences naturelles et en génie du Canada (CRSNG), [numéro de référence RGPIN-2020-03912]. This project was funded in part by the Government of Ontario .","OA_type":"hybrid","oa_version":"Published Version","title":"On heroes in digraphs with forbidden induced forests","date_created":"2025-01-05T23:01:55Z","publication_identifier":{"issn":["0195-6698"]},"arxiv":1,"file":[{"content_type":"application/pdf","success":1,"date_created":"2025-04-16T09:16:25Z","file_size":1110657,"access_level":"open_access","relation":"main_file","creator":"dernst","date_updated":"2025-04-16T09:16:25Z","file_id":"19577","checksum":"2c75f78f40ebb93d16fe3765bda2905a","file_name":"2025_EuropJournCombinatorics_Carbonero.pdf"}],"publication_status":"published","scopus_import":"1","status":"public","isi":1,"publication":"European Journal of Combinatorics","date_updated":"2025-05-19T14:06:00Z","file_date_updated":"2025-04-16T09:16:25Z","OA_place":"publisher","date_published":"2025-03-01T00:00:00Z","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","ddc":["510"],"year":"2025","intvolume":"       125","article_number":"104104","day":"01","citation":{"chicago":"Carbonero, Alvaro, Hidde Koerts, Benjamin Moore, and Sophie Spirkl. “On Heroes in Digraphs with Forbidden Induced Forests.” <i>European Journal of Combinatorics</i>. Elsevier, 2025. <a href=\"https://doi.org/10.1016/j.ejc.2024.104104\">https://doi.org/10.1016/j.ejc.2024.104104</a>.","ama":"Carbonero A, Koerts H, Moore B, Spirkl S. On heroes in digraphs with forbidden induced forests. <i>European Journal of Combinatorics</i>. 2025;125. doi:<a href=\"https://doi.org/10.1016/j.ejc.2024.104104\">10.1016/j.ejc.2024.104104</a>","ista":"Carbonero A, Koerts H, Moore B, Spirkl S. 2025. On heroes in digraphs with forbidden induced forests. European Journal of Combinatorics. 125, 104104.","apa":"Carbonero, A., Koerts, H., Moore, B., &#38; Spirkl, S. (2025). On heroes in digraphs with forbidden induced forests. <i>European Journal of Combinatorics</i>. Elsevier. <a href=\"https://doi.org/10.1016/j.ejc.2024.104104\">https://doi.org/10.1016/j.ejc.2024.104104</a>","mla":"Carbonero, Alvaro, et al. “On Heroes in Digraphs with Forbidden Induced Forests.” <i>European Journal of Combinatorics</i>, vol. 125, 104104, Elsevier, 2025, doi:<a href=\"https://doi.org/10.1016/j.ejc.2024.104104\">10.1016/j.ejc.2024.104104</a>.","short":"A. Carbonero, H. Koerts, B. Moore, S. Spirkl, European Journal of Combinatorics 125 (2025).","ieee":"A. Carbonero, H. Koerts, B. Moore, and S. Spirkl, “On heroes in digraphs with forbidden induced forests,” <i>European Journal of Combinatorics</i>, vol. 125. Elsevier, 2025."},"has_accepted_license":"1","quality_controlled":"1","type":"journal_article","external_id":{"arxiv":["2306.04710"],"isi":["001400113700001"]},"_id":"18753","language":[{"iso":"eng"}],"abstract":[{"lang":"eng","text":"We continue a line of research which studies which hereditary families of digraphs have bounded dichromatic number. For a class of digraphs  C, a hero in  C  is any digraph  H\r\n  such that  H -free digraphs in  C  have bounded dichromatic number. We show that if  F\r\n  is an oriented star of degree at least five, the only heroes for the class of  F -free digraphs are transitive tournaments. For oriented stars  F  of degree exactly four, we show the only heroes in  F -free digraphs are transitive tournaments, or possibly special joins of transitive tournaments. Aboulker et al. characterized the set of heroes of  {H,K1+P2→} -free digraphs almost completely, and we show the same characterization for the class of  {H,rK1+P3→} -free digraphs. Lastly, we show that if we forbid two \"valid\" orientations of brooms, then every transitive tournament is a hero for this class of digraphs."}]},{"has_accepted_license":"1","day":"01","citation":{"ista":"Cortés PP, Kumar P, Moore B, Ossona de Mendez P, Quiroz DA. 2025. Subchromatic numbers of powers of graphs with excluded minors. Discrete Mathematics. 348(4), 114377.","ama":"Cortés PP, Kumar P, Moore B, Ossona de Mendez P, Quiroz DA. Subchromatic numbers of powers of graphs with excluded minors. <i>Discrete Mathematics</i>. 2025;348(4). doi:<a href=\"https://doi.org/10.1016/j.disc.2024.114377\">10.1016/j.disc.2024.114377</a>","chicago":"Cortés, Pedro P., Pankaj Kumar, Benjamin Moore, Patrice Ossona de Mendez, and Daniel A. Quiroz. “Subchromatic Numbers of Powers of Graphs with Excluded Minors.” <i>Discrete Mathematics</i>. Elsevier, 2025. <a href=\"https://doi.org/10.1016/j.disc.2024.114377\">https://doi.org/10.1016/j.disc.2024.114377</a>.","short":"P.P. Cortés, P. Kumar, B. Moore, P. Ossona de Mendez, D.A. Quiroz, Discrete Mathematics 348 (2025).","ieee":"P. P. Cortés, P. Kumar, B. Moore, P. Ossona de Mendez, and D. A. Quiroz, “Subchromatic numbers of powers of graphs with excluded minors,” <i>Discrete Mathematics</i>, vol. 348, no. 4. Elsevier, 2025.","mla":"Cortés, Pedro P., et al. “Subchromatic Numbers of Powers of Graphs with Excluded Minors.” <i>Discrete Mathematics</i>, vol. 348, no. 4, 114377, Elsevier, 2025, doi:<a href=\"https://doi.org/10.1016/j.disc.2024.114377\">10.1016/j.disc.2024.114377</a>.","apa":"Cortés, P. P., Kumar, P., Moore, B., Ossona de Mendez, P., &#38; Quiroz, D. A. (2025). Subchromatic numbers of powers of graphs with excluded minors. <i>Discrete Mathematics</i>. Elsevier. <a href=\"https://doi.org/10.1016/j.disc.2024.114377\">https://doi.org/10.1016/j.disc.2024.114377</a>"},"language":[{"iso":"eng"}],"_id":"19002","abstract":[{"lang":"eng","text":"A k-subcolouring of a graph G is a function f : V (G) → {0,...,k − 1} such that the set of\r\nvertices coloured i induce a disjoint union of cliques. The subchromatic number, χsub(G),\r\nis the minimum k such that G admits a k-subcolouring. Nešetril, ˇ Ossona de Mendez,\r\nPilipczuk, and Zhu (2020), recently raised the problem of finding tight upper bounds for\r\nχsub(G2) when G is planar. We show that χsub(G2) ≤ 43 when G is planar, improving\r\ntheir bound of 135. We give even better bounds when the planar graph G has larger girth.\r\nMoreover, we show that χsub(G3) ≤ 95, improving the previous bound of 364. For these\r\nwe adapt some recent techniques of Almulhim and Kierstead (2022), while also extending\r\nthe decompositions of triangulated planar graphs of Van den Heuvel, Ossona de Mendez,\r\nQuiroz, Rabinovich and Siebertz (2017), to planar graphs of arbitrary girth. Note that these\r\ndecompositions are the precursors of the graph product structure theorem of planar graphs.\r\nWe give improved bounds for χsub(Gp) for all p ≥ 2, whenever G has bounded treewidth,\r\nbounded simple treewidth, bounded genus, or excludes a clique or biclique as a minor.\r\nFor this we introduce a family of parameters which form a gradation between the strong\r\nand the weak colouring numbers. We give upper bounds for these parameters for graphs\r\ncoming from such classes.\r\nFinally, we give a 2-approximation algorithm for the subchromatic number of graphs\r\nhaving a layering in which each layer has bounded cliquewidth and this layering is\r\ncomputable in polynomial time (like the class of all dth powers of planar graphs, for fixed\r\nd). This algorithm works even if the power p and the graph G is unknown."}],"external_id":{"isi":["001401656900001"],"arxiv":["2306.02195"]},"type":"journal_article","quality_controlled":"1","date_published":"2025-04-01T00:00:00Z","OA_place":"publisher","intvolume":"       348","article_number":"114377","year":"2025","ddc":["510"],"user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","date_updated":"2025-09-30T10:25:15Z","publication":"Discrete Mathematics","isi":1,"file_date_updated":"2025-05-05T12:56:12Z","issue":"4","scopus_import":"1","status":"public","file":[{"content_type":"application/pdf","success":1,"date_created":"2025-05-05T12:56:12Z","file_size":850988,"access_level":"open_access","file_id":"19657","creator":"dernst","relation":"main_file","date_updated":"2025-05-05T12:56:12Z","checksum":"6723cbb02b6aea0d05f37d167da00c03","file_name":"2025_DiscreteMath_Cortes.pdf"}],"publication_status":"published","title":"Subchromatic numbers of powers of graphs with excluded minors","date_created":"2025-02-05T06:51:08Z","oa_version":"Published Version","OA_type":"hybrid","publication_identifier":{"issn":["0012-365X"]},"arxiv":1,"author":[{"first_name":"Pedro P.","full_name":"Cortés, Pedro P.","last_name":"Cortés"},{"first_name":"Pankaj","last_name":"Kumar","full_name":"Kumar, Pankaj"},{"full_name":"Moore, Benjamin","last_name":"Moore","first_name":"Benjamin","id":"6dc1a1be-bf1c-11ed-8d2b-d044840f49d6"},{"first_name":"Patrice","full_name":"Ossona de Mendez, Patrice","last_name":"Ossona de Mendez"},{"last_name":"Quiroz","full_name":"Quiroz, Daniel A.","first_name":"Daniel A."}],"volume":348,"article_type":"original","department":[{"_id":"MaKw"}],"month":"04","acknowledgement":"We thank an anonymous referee for pointing out an error in an earlier version of Theorem 3.1. We also thank an anonymous referee for pointing out numerous typos in an earlier version of the paper.","doi":"10.1016/j.disc.2024.114377","oa":1,"tmp":{"short":"CC BY (4.0)","image":"/images/cc_by.png","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)"},"corr_author":"1","article_processing_charge":"Yes (via OA deal)","publisher":"Elsevier"},{"publisher":"Elsevier","corr_author":"1","article_processing_charge":"No","article_type":"original","department":[{"_id":"MaKw"}],"month":"06","volume":347,"author":[{"full_name":"Campbell, Rutger","last_name":"Campbell","first_name":"Rutger"},{"last_name":"Hörsch","full_name":"Hörsch, Florian","first_name":"Florian"},{"full_name":"Moore, Benjamin","last_name":"Moore","first_name":"Benjamin","id":"6dc1a1be-bf1c-11ed-8d2b-d044840f49d6"}],"acknowledgement":"We wish to thank Dániel Marx and András Sebő for making us aware of the results in [8] and some clarifications on them.","oa":1,"doi":"10.1016/j.disc.2024.113962","oa_version":"Preprint","date_created":"2024-03-24T23:00:58Z","title":"Decompositions into two linear forests of bounded lengths","arxiv":1,"publication_identifier":{"issn":["0012-365X"]},"publication_status":"published","scopus_import":"1","issue":"6","status":"public","isi":1,"date_updated":"2025-09-04T13:10:26Z","publication":"Discrete Mathematics","main_file_link":[{"open_access":"1","url":"https://doi.org/10.48550/arXiv.2301.11615"}],"date_published":"2024-06-01T00:00:00Z","year":"2024","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","article_number":"113962","intvolume":"       347","citation":{"short":"R. Campbell, F. Hörsch, B. Moore, Discrete Mathematics 347 (2024).","ieee":"R. Campbell, F. Hörsch, and B. Moore, “Decompositions into two linear forests of bounded lengths,” <i>Discrete Mathematics</i>, vol. 347, no. 6. Elsevier, 2024.","mla":"Campbell, Rutger, et al. “Decompositions into Two Linear Forests of Bounded Lengths.” <i>Discrete Mathematics</i>, vol. 347, no. 6, 113962, Elsevier, 2024, doi:<a href=\"https://doi.org/10.1016/j.disc.2024.113962\">10.1016/j.disc.2024.113962</a>.","apa":"Campbell, R., Hörsch, F., &#38; Moore, B. (2024). Decompositions into two linear forests of bounded lengths. <i>Discrete Mathematics</i>. Elsevier. <a href=\"https://doi.org/10.1016/j.disc.2024.113962\">https://doi.org/10.1016/j.disc.2024.113962</a>","ista":"Campbell R, Hörsch F, Moore B. 2024. Decompositions into two linear forests of bounded lengths. Discrete Mathematics. 347(6), 113962.","ama":"Campbell R, Hörsch F, Moore B. Decompositions into two linear forests of bounded lengths. <i>Discrete Mathematics</i>. 2024;347(6). doi:<a href=\"https://doi.org/10.1016/j.disc.2024.113962\">10.1016/j.disc.2024.113962</a>","chicago":"Campbell, Rutger, Florian Hörsch, and Benjamin Moore. “Decompositions into Two Linear Forests of Bounded Lengths.” <i>Discrete Mathematics</i>. Elsevier, 2024. <a href=\"https://doi.org/10.1016/j.disc.2024.113962\">https://doi.org/10.1016/j.disc.2024.113962</a>."},"day":"01","type":"journal_article","quality_controlled":"1","_id":"15163","abstract":[{"lang":"eng","text":"For some k∈Z≥0∪{∞}, we call a linear forest k-bounded if each of its components has at most k edges. We will say a (k,ℓ)-bounded linear forest decomposition of a graph G is a partition of E(G) into the edge sets of two linear forests Fk,Fℓ where Fk is k-bounded and Fℓ is ℓ-bounded. We show that the problem of deciding whether a given graph has such a decomposition is NP-complete if both k and ℓ are at least 2, NP-complete if k≥9 and ℓ=1, and is in P for (k,ℓ)=(2,1). Before this, the only known NP-complete cases were the (2,2) and (3,3) cases. Our hardness result answers a question of Bermond et al. from 1984. We also show that planar graphs of girth at least nine decompose into a linear forest and a matching, which in particular is stronger than 3-edge-colouring such graphs."}],"language":[{"iso":"eng"}],"external_id":{"arxiv":["2301.11615"],"isi":["001226893800001"]}}]