[{"status":"public","date_published":"2025-04-01T00:00:00Z","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","date_created":"2025-02-05T06:51:08Z","type":"journal_article","article_type":"original","publisher":"Elsevier","year":"2025","ddc":["510"],"issue":"4","_id":"19002","file":[{"date_updated":"2025-05-05T12:56:12Z","access_level":"open_access","checksum":"6723cbb02b6aea0d05f37d167da00c03","file_id":"19657","file_name":"2025_DiscreteMath_Cortes.pdf","file_size":850988,"creator":"dernst","relation":"main_file","success":1,"content_type":"application/pdf","date_created":"2025-05-05T12:56:12Z"}],"article_number":"114377","file_date_updated":"2025-05-05T12:56:12Z","oa_version":"Published Version","doi":"10.1016/j.disc.2024.114377","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)"},"date_updated":"2025-09-30T10:25:15Z","external_id":{"arxiv":["2306.02195"],"isi":["001401656900001"]},"department":[{"_id":"MaKw"}],"article_processing_charge":"Yes (via OA deal)","isi":1,"citation":{"short":"P.P. Cortés, P. Kumar, B. Moore, P. Ossona de Mendez, D.A. Quiroz, Discrete Mathematics 348 (2025).","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>","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>","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>.","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.","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>.","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."},"author":[{"first_name":"Pedro P.","last_name":"Cortés","full_name":"Cortés, Pedro P."},{"full_name":"Kumar, Pankaj","last_name":"Kumar","first_name":"Pankaj"},{"full_name":"Moore, Benjamin","id":"6dc1a1be-bf1c-11ed-8d2b-d044840f49d6","first_name":"Benjamin","last_name":"Moore"},{"last_name":"Ossona de Mendez","first_name":"Patrice","full_name":"Ossona de Mendez, Patrice"},{"last_name":"Quiroz","first_name":"Daniel A.","full_name":"Quiroz, Daniel A."}],"language":[{"iso":"eng"}],"arxiv":1,"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.","oa":1,"publication_identifier":{"issn":["0012-365X"]},"volume":348,"month":"04","scopus_import":"1","has_accepted_license":"1","corr_author":"1","title":"Subchromatic numbers of powers of graphs with excluded minors","publication_status":"published","OA_place":"publisher","publication":"Discrete Mathematics","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."}],"intvolume":"       348","OA_type":"hybrid","quality_controlled":"1","day":"01"},{"doi":"10.1016/j.disc.2024.114373","oa_version":"Preprint","_id":"22163","article_number":"114373","das_tickbox":"1","external_id":{"arxiv":["2404.01057"]},"extern":"1","date_updated":"2026-07-14T08:17:17Z","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","date_created":"2026-06-29T10:53:05Z","keyword":["Nearly orthogonal sets","Ramsey theory","Finite fields"],"date_published":"2025-04-01T00:00:00Z","status":"public","issue":"4","year":"2025","publisher":"Elsevier","article_type":"original","type":"journal_article","OA_type":"green","intvolume":"       348","abstract":[{"lang":"eng","text":"For a field F and integers d and k, a set A ⊆ Fd is called k-nearly orthogonal if its\r\nmembers are non-self-orthogonal and every k + 1 vectors of A include an orthogonal pair.\r\nWe prove that for every prime p there exists some δ = δ(p)> 0, such that for every field\r\nF of characteristic p and for all integers k ≥ 2 and d ≥ k, there exists a k-nearly orthogonal\r\nset of at least dδ·k/ logk vectors of Fd. The size of the set is optimal up to the logk term\r\nin the exponent. We further prove two extensions of this result. In the first, we provide a\r\nlarge set A of non-self-orthogonal vectors of Fd such that for every two subsets of A of\r\nsize k+1 each, some vector of one of the subsets is orthogonal to some vector of the other.\r\nIn the second extension, every k + 1 vectors of the produced set A include ℓ + 1 pairwise\r\northogonal vectors for an arbitrary fixed integer 1 ≤ ℓ ≤ k. The proofs involve probabilistic\r\nand spectral arguments and the hypergraph container method"}],"publication":"Discrete Mathematics","OA_place":"repository","title":"Larger nearly orthogonal sets over finite fields","publication_status":"published","main_file_link":[{"open_access":"1","url":"https://doi.org/10.48550/arXiv.2404.01057 "}],"day":"01","quality_controlled":"1","oa":1,"arxiv":1,"language":[{"iso":"eng"}],"author":[{"last_name":"Haviv","first_name":"Ishay","full_name":"Haviv, Ishay"},{"first_name":"Sam","last_name":"Mattheus","full_name":"Mattheus, Sam"},{"first_name":"Aleksa","last_name":"Milojević","full_name":"Milojević, Aleksa"},{"last_name":"Wigderson","first_name":"Yuval","id":"2d0023a0-1567-11f0-833d-d5c1e476d4b5","full_name":"Wigderson, Yuval"}],"citation":{"chicago":"Haviv, Ishay, Sam Mattheus, Aleksa Milojević, and Yuval Wigderson. “Larger Nearly Orthogonal Sets over Finite Fields.” <i>Discrete Mathematics</i>. Elsevier, 2025. <a href=\"https://doi.org/10.1016/j.disc.2024.114373\">https://doi.org/10.1016/j.disc.2024.114373</a>.","ista":"Haviv I, Mattheus S, Milojević A, Wigderson Y. 2025. Larger nearly orthogonal sets over finite fields. Discrete Mathematics. 348(4), 114373.","apa":"Haviv, I., Mattheus, S., Milojević, A., &#38; Wigderson, Y. (2025). Larger nearly orthogonal sets over finite fields. <i>Discrete Mathematics</i>. Elsevier. <a href=\"https://doi.org/10.1016/j.disc.2024.114373\">https://doi.org/10.1016/j.disc.2024.114373</a>","ama":"Haviv I, Mattheus S, Milojević A, Wigderson Y. Larger nearly orthogonal sets over finite fields. <i>Discrete Mathematics</i>. 2025;348(4). doi:<a href=\"https://doi.org/10.1016/j.disc.2024.114373\">10.1016/j.disc.2024.114373</a>","short":"I. Haviv, S. Mattheus, A. Milojević, Y. Wigderson, Discrete Mathematics 348 (2025).","mla":"Haviv, Ishay, et al. “Larger Nearly Orthogonal Sets over Finite Fields.” <i>Discrete Mathematics</i>, vol. 348, no. 4, 114373, Elsevier, 2025, doi:<a href=\"https://doi.org/10.1016/j.disc.2024.114373\">10.1016/j.disc.2024.114373</a>.","ieee":"I. Haviv, S. Mattheus, A. Milojević, and Y. Wigderson, “Larger nearly orthogonal sets over finite fields,” <i>Discrete Mathematics</i>, vol. 348, no. 4. Elsevier, 2025."},"article_processing_charge":"No","month":"04","scopus_import":"1","volume":348,"publication_identifier":{"issn":["0012-365X"]}},{"year":"2024","issue":"6","article_type":"original","type":"journal_article","publisher":"Elsevier","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","date_created":"2024-03-24T23:00:58Z","status":"public","date_published":"2024-06-01T00:00:00Z","department":[{"_id":"MaKw"}],"date_updated":"2025-09-04T13:10:26Z","external_id":{"isi":["001226893800001"],"arxiv":["2301.11615"]},"doi":"10.1016/j.disc.2024.113962","_id":"15163","article_number":"113962","oa_version":"Preprint","volume":347,"month":"06","scopus_import":"1","publication_identifier":{"issn":["0012-365X"]},"arxiv":1,"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,"citation":{"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>.","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.","short":"R. Campbell, F. Hörsch, B. Moore, Discrete Mathematics 347 (2024).","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>","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.","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>."},"article_processing_charge":"No","isi":1,"author":[{"first_name":"Rutger","last_name":"Campbell","full_name":"Campbell, Rutger"},{"first_name":"Florian","last_name":"Hörsch","full_name":"Hörsch, Florian"},{"full_name":"Moore, Benjamin","first_name":"Benjamin","id":"6dc1a1be-bf1c-11ed-8d2b-d044840f49d6","last_name":"Moore"}],"language":[{"iso":"eng"}],"main_file_link":[{"open_access":"1","url":"https://doi.org/10.48550/arXiv.2301.11615"}],"quality_controlled":"1","day":"01","corr_author":"1","title":"Decompositions into two linear forests of bounded lengths","publication_status":"published","publication":"Discrete Mathematics","abstract":[{"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.","lang":"eng"}],"intvolume":"       347"},{"publisher":"Elsevier","article_type":"letter_note","type":"journal_article","issue":"6","year":"2023","date_published":"2023-06-01T00:00:00Z","status":"public","date_created":"2023-02-26T23:01:00Z","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","external_id":{"arxiv":["2201.10892"],"isi":["001189844500001"]},"related_material":{"record":[{"id":"13331","relation":"dissertation_contains","status":"public"}]},"date_updated":"2026-04-07T13:29:28Z","department":[{"_id":"UlWa"},{"_id":"GradSch"}],"oa_version":"Preprint","_id":"12680","article_number":"113363","doi":"10.1016/j.disc.2023.113363","publication_identifier":{"issn":["0012-365X"]},"scopus_import":"1","month":"06","volume":346,"language":[{"iso":"eng"}],"author":[{"last_name":"Ivanov","id":"87744F66-5C6F-11EA-AFE0-D16B3DDC885E","first_name":"Grigory","orcid":"0000-0002-5021-3982","full_name":"Ivanov, Grigory"},{"orcid":"0009-0008-0457-9730","full_name":"Köse, Seyda","last_name":"Köse","id":"8ba3170d-dc85-11ea-9058-c4251c96a6eb","first_name":"Seyda"}],"isi":1,"article_processing_charge":"No","citation":{"ieee":"G. Ivanov and S. Köse, “Erdős-Ko-Rado and Hilton-Milner theorems for two-forms,” <i>Discrete Mathematics</i>, vol. 346, no. 6. Elsevier, 2023.","mla":"Ivanov, Grigory, and Seyda Köse. “Erdős-Ko-Rado and Hilton-Milner Theorems for Two-Forms.” <i>Discrete Mathematics</i>, vol. 346, no. 6, 113363, Elsevier, 2023, doi:<a href=\"https://doi.org/10.1016/j.disc.2023.113363\">10.1016/j.disc.2023.113363</a>.","short":"G. Ivanov, S. Köse, Discrete Mathematics 346 (2023).","ista":"Ivanov G, Köse S. 2023. Erdős-Ko-Rado and Hilton-Milner theorems for two-forms. Discrete Mathematics. 346(6), 113363.","chicago":"Ivanov, Grigory, and Seyda Köse. “Erdős-Ko-Rado and Hilton-Milner Theorems for Two-Forms.” <i>Discrete Mathematics</i>. Elsevier, 2023. <a href=\"https://doi.org/10.1016/j.disc.2023.113363\">https://doi.org/10.1016/j.disc.2023.113363</a>.","ama":"Ivanov G, Köse S. Erdős-Ko-Rado and Hilton-Milner theorems for two-forms. <i>Discrete Mathematics</i>. 2023;346(6). doi:<a href=\"https://doi.org/10.1016/j.disc.2023.113363\">10.1016/j.disc.2023.113363</a>","apa":"Ivanov, G., &#38; Köse, S. (2023). Erdős-Ko-Rado and Hilton-Milner theorems for two-forms. <i>Discrete Mathematics</i>. Elsevier. <a href=\"https://doi.org/10.1016/j.disc.2023.113363\">https://doi.org/10.1016/j.disc.2023.113363</a>"},"oa":1,"arxiv":1,"day":"01","quality_controlled":"1","main_file_link":[{"open_access":"1","url":" https://doi.org/10.48550/arXiv.2201.10892"}],"abstract":[{"lang":"eng","text":"The celebrated Erdős–Ko–Rado theorem about the maximal size of an intersecting family of r-element subsets of  was extended to the setting of exterior algebra in [5, Theorem 2.3] and in [6, Theorem 1.4]. However, the equality case has not been settled yet. In this short note, we show that the extension of the Erdős–Ko–Rado theorem and the characterization of the equality case therein, as well as those of the Hilton–Milner theorem to the setting of exterior algebra in the simplest non-trivial case of two-forms follow from a folklore puzzle about possible arrangements of an intersecting family of lines."}],"intvolume":"       346","publication":"Discrete Mathematics","publication_status":"published","corr_author":"1","title":"Erdős-Ko-Rado and Hilton-Milner theorems for two-forms"},{"day":"01","quality_controlled":"1","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1808.09165"}],"intvolume":"       344","abstract":[{"text":"We study properties of the volume of projections of the n-dimensional\r\ncross-polytope $\\crosp^n = \\{ x \\in \\R^n \\mid |x_1| + \\dots + |x_n| \\leqslant 1\\}.$ We prove that the projection of $\\crosp^n$ onto a k-dimensional coordinate subspace has the maximum possible volume for k=2 and for k=3.\r\nWe obtain the exact lower bound on the volume of such a projection onto a two-dimensional plane. Also, we show that there exist local maxima which are not global ones for the volume of a projection of $\\crosp^n$ onto a k-dimensional subspace for any n>k⩾2.","lang":"eng"}],"publication":"Discrete Mathematics","publication_status":"published","title":"On the volume of projections of the cross-polytope","publication_identifier":{"issn":["0012-365X"]},"scopus_import":"1","month":"05","volume":344,"language":[{"iso":"eng"}],"author":[{"first_name":"Grigory","id":"87744F66-5C6F-11EA-AFE0-D16B3DDC885E","last_name":"Ivanov","full_name":"Ivanov, Grigory"}],"article_processing_charge":"No","isi":1,"citation":{"mla":"Ivanov, Grigory. “On the Volume of Projections of the Cross-Polytope.” <i>Discrete Mathematics</i>, vol. 344, no. 5, 112312, Elsevier, 2021, doi:<a href=\"https://doi.org/10.1016/j.disc.2021.112312\">10.1016/j.disc.2021.112312</a>.","ieee":"G. Ivanov, “On the volume of projections of the cross-polytope,” <i>Discrete Mathematics</i>, vol. 344, no. 5. Elsevier, 2021.","ista":"Ivanov G. 2021. On the volume of projections of the cross-polytope. Discrete Mathematics. 344(5), 112312.","chicago":"Ivanov, Grigory. “On the Volume of Projections of the Cross-Polytope.” <i>Discrete Mathematics</i>. Elsevier, 2021. <a href=\"https://doi.org/10.1016/j.disc.2021.112312\">https://doi.org/10.1016/j.disc.2021.112312</a>.","ama":"Ivanov G. On the volume of projections of the cross-polytope. <i>Discrete Mathematics</i>. 2021;344(5). doi:<a href=\"https://doi.org/10.1016/j.disc.2021.112312\">10.1016/j.disc.2021.112312</a>","apa":"Ivanov, G. (2021). On the volume of projections of the cross-polytope. <i>Discrete Mathematics</i>. Elsevier. <a href=\"https://doi.org/10.1016/j.disc.2021.112312\">https://doi.org/10.1016/j.disc.2021.112312</a>","short":"G. Ivanov, Discrete Mathematics 344 (2021)."},"oa":1,"acknowledgement":"Research was supported by the Russian Foundation for Basic Research, project 18-01-00036A (Theorems 1.5 and 5.3) and by the Ministry of Education and Science of the Russian Federation in the framework of MegaGrant no 075-15-2019-1926 (Theorems 1.2 and 7.3).","arxiv":1,"external_id":{"arxiv":["1808.09165"],"isi":["000633365200001"]},"date_updated":"2025-07-10T12:01:36Z","department":[{"_id":"UlWa"}],"oa_version":"Preprint","article_number":"112312","_id":"9098","doi":"10.1016/j.disc.2021.112312","publisher":"Elsevier","type":"journal_article","article_type":"original","issue":"5","year":"2021","date_published":"2021-05-01T00:00:00Z","status":"public","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","date_created":"2021-02-07T23:01:12Z"},{"scopus_import":"1","month":"11","volume":342,"publication_identifier":{"issn":["0012-365X"]},"arxiv":1,"oa":1,"article_processing_charge":"No","isi":1,"citation":{"short":"A. Silva, A.M. Arroyo Guevara, B. Richter, O. Lee, Discrete Mathematics 342 (2019) 3201–3207.","chicago":"Silva, André , Alan M Arroyo Guevara, Bruce Richter, and Orlando Lee. “Graphs with at Most One Crossing.” <i>Discrete Mathematics</i>. Elsevier, 2019. <a href=\"https://doi.org/10.1016/j.disc.2019.06.031\">https://doi.org/10.1016/j.disc.2019.06.031</a>.","ista":"Silva A, Arroyo Guevara AM, Richter B, Lee O. 2019. Graphs with at most one crossing. Discrete Mathematics. 342(11), 3201–3207.","ama":"Silva A, Arroyo Guevara AM, Richter B, Lee O. Graphs with at most one crossing. <i>Discrete Mathematics</i>. 2019;342(11):3201-3207. doi:<a href=\"https://doi.org/10.1016/j.disc.2019.06.031\">10.1016/j.disc.2019.06.031</a>","apa":"Silva, A., Arroyo Guevara, A. M., Richter, B., &#38; Lee, O. (2019). Graphs with at most one crossing. <i>Discrete Mathematics</i>. Elsevier. <a href=\"https://doi.org/10.1016/j.disc.2019.06.031\">https://doi.org/10.1016/j.disc.2019.06.031</a>","mla":"Silva, André, et al. “Graphs with at Most One Crossing.” <i>Discrete Mathematics</i>, vol. 342, no. 11, Elsevier, 2019, pp. 3201–07, doi:<a href=\"https://doi.org/10.1016/j.disc.2019.06.031\">10.1016/j.disc.2019.06.031</a>.","ieee":"A. Silva, A. M. Arroyo Guevara, B. Richter, and O. Lee, “Graphs with at most one crossing,” <i>Discrete Mathematics</i>, vol. 342, no. 11. Elsevier, pp. 3201–3207, 2019."},"page":"3201-3207","language":[{"iso":"eng"}],"project":[{"_id":"26366136-B435-11E9-9278-68D0E5697425","name":"Reglas de Conectividad funcional en el hipocampo"},{"_id":"260C2330-B435-11E9-9278-68D0E5697425","name":"ISTplus - Postdoctoral Fellowships","call_identifier":"H2020","grant_number":"754411"}],"author":[{"last_name":"Silva","first_name":"André ","full_name":"Silva, André "},{"last_name":"Arroyo Guevara","id":"3207FDC6-F248-11E8-B48F-1D18A9856A87","first_name":"Alan M","orcid":"0000-0003-2401-8670","full_name":"Arroyo Guevara, Alan M"},{"full_name":"Richter, Bruce","first_name":"Bruce","last_name":"Richter"},{"full_name":"Lee, Orlando","first_name":"Orlando","last_name":"Lee"}],"main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1901.09955"}],"quality_controlled":"1","day":"01","ec_funded":1,"title":"Graphs with at most one crossing","publication_status":"published","abstract":[{"lang":"eng","text":"The crossing number of a graph G is the least number of crossings over all possible drawings of G. We present a structural characterization of graphs with crossing number one."}],"intvolume":"       342","publication":"Discrete Mathematics","year":"2019","issue":"11","publisher":"Elsevier","type":"journal_article","date_created":"2019-07-14T21:59:20Z","user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","date_published":"2019-11-01T00:00:00Z","status":"public","department":[{"_id":"UlWa"}],"date_updated":"2025-04-14T07:44:06Z","external_id":{"isi":["000486358100025"],"arxiv":["1901.09955"]},"doi":"10.1016/j.disc.2019.06.031","_id":"6638","oa_version":"Preprint"},{"oa_version":"None","_id":"4065","doi":"10.1016/0012-365X(90)90147-A","date_updated":"2022-02-22T15:45:55Z","extern":"1","status":"public","date_published":"1990-04-15T00:00:00Z","user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","date_created":"2018-12-11T12:06:44Z","article_type":"original","type":"journal_article","publisher":"Elsevier","issue":"2","year":"1990","publication":"Discrete Mathematics","intvolume":"        81","abstract":[{"lang":"eng","text":"We prove that given n⩾3 convex, compact, and pairwise disjoint sets in the plane, they may be covered with n non-overlapping convex polygons with a total of not more than 6n−9 sides, and with not more than 3n−6 distinct slopes. Furthermore, we construct sets that require 6n−9 sides and 3n−6 slopes for n⩾3. The upper bound on the number of slopes implies a new bound on a recently studied transversal problem."}],"title":"Covering convex sets with non-overlapping polygons","publication_status":"published","day":"15","quality_controlled":"1","main_file_link":[{"url":"https://www.sciencedirect.com/science/article/pii/0012365X9090147A?via%3Dihub"}],"author":[{"first_name":"Herbert","id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","last_name":"Edelsbrunner","full_name":"Edelsbrunner, Herbert","orcid":"0000-0002-9823-6833"},{"first_name":"Arch","last_name":"Robison","full_name":"Robison, Arch"},{"first_name":"Xiao","last_name":"Shen","full_name":"Shen, Xiao"}],"language":[{"iso":"eng"}],"page":"153 - 164","article_processing_charge":"No","citation":{"short":"H. Edelsbrunner, A. Robison, X. Shen, Discrete Mathematics 81 (1990) 153–164.","ista":"Edelsbrunner H, Robison A, Shen X. 1990. Covering convex sets with non-overlapping polygons. Discrete Mathematics. 81(2), 153–164.","chicago":"Edelsbrunner, Herbert, Arch Robison, and Xiao Shen. “Covering Convex Sets with Non-Overlapping Polygons.” <i>Discrete Mathematics</i>. Elsevier, 1990. <a href=\"https://doi.org/10.1016/0012-365X(90)90147-A\">https://doi.org/10.1016/0012-365X(90)90147-A</a>.","ama":"Edelsbrunner H, Robison A, Shen X. Covering convex sets with non-overlapping polygons. <i>Discrete Mathematics</i>. 1990;81(2):153-164. doi:<a href=\"https://doi.org/10.1016/0012-365X(90)90147-A\">10.1016/0012-365X(90)90147-A</a>","apa":"Edelsbrunner, H., Robison, A., &#38; Shen, X. (1990). Covering convex sets with non-overlapping polygons. <i>Discrete Mathematics</i>. Elsevier. <a href=\"https://doi.org/10.1016/0012-365X(90)90147-A\">https://doi.org/10.1016/0012-365X(90)90147-A</a>","ieee":"H. Edelsbrunner, A. Robison, and X. Shen, “Covering convex sets with non-overlapping polygons,” <i>Discrete Mathematics</i>, vol. 81, no. 2. Elsevier, pp. 153–164, 1990.","mla":"Edelsbrunner, Herbert, et al. “Covering Convex Sets with Non-Overlapping Polygons.” <i>Discrete Mathematics</i>, vol. 81, no. 2, Elsevier, 1990, pp. 153–64, doi:<a href=\"https://doi.org/10.1016/0012-365X(90)90147-A\">10.1016/0012-365X(90)90147-A</a>."},"publist_id":"2060","acknowledgement":"The first author acknowledges the support by Amoco Fnd. Fat. Dev. Comput. Sci. l-6-44862. Work on this paper by the second author was supported by a Shell Fellowship in Computer Science. The third author as supported by the office of Naval Research under grant NOOO14-86K-0416. ","publication_identifier":{"issn":["0012-365X"],"eissn":["1872-681X"]},"volume":81,"scopus_import":"1","month":"04"},{"publication_status":"published","title":"The complexity of cells in 3-dimensional arrangements","intvolume":"        60","abstract":[{"text":"A set of m planes dissects E3 into cells, facets, edges and vertices. Letting deg(c) be the number of facets that bound a cellc, we give exact and asymptotic bounds on the maximum of ∈cinCdeg(c), if C is a family of cells of the arrangement with fixed cardinality.","lang":"eng"}],"publication":"Discrete Mathematics","quality_controlled":"1","day":"01","acknowledgement":"Research reported in the paper was conducted while the second author was visiting the Technical University of Graz. Support provided by the Technical University for this visit is gratefully acknowledged. ","publist_id":"2019","citation":{"ista":"Edelsbrunner H, Haussler D. 1986. The complexity of cells in 3-dimensional arrangements. Discrete Mathematics. 60(C), 139–146.","chicago":"Edelsbrunner, Herbert, and David Haussler. “The Complexity of Cells in 3-Dimensional Arrangements.” <i>Discrete Mathematics</i>. Elsevier, 1986. <a href=\"https://doi.org/10.1016/0012-365X(86)90008-7\">https://doi.org/10.1016/0012-365X(86)90008-7</a>.","apa":"Edelsbrunner, H., &#38; Haussler, D. (1986). The complexity of cells in 3-dimensional arrangements. <i>Discrete Mathematics</i>. Elsevier. <a href=\"https://doi.org/10.1016/0012-365X(86)90008-7\">https://doi.org/10.1016/0012-365X(86)90008-7</a>","ama":"Edelsbrunner H, Haussler D. The complexity of cells in 3-dimensional arrangements. <i>Discrete Mathematics</i>. 1986;60(C):139-146. doi:<a href=\"https://doi.org/10.1016/0012-365X(86)90008-7\">10.1016/0012-365X(86)90008-7</a>","short":"H. Edelsbrunner, D. Haussler, Discrete Mathematics 60 (1986) 139–146.","mla":"Edelsbrunner, Herbert, and David Haussler. “The Complexity of Cells in 3-Dimensional Arrangements.” <i>Discrete Mathematics</i>, vol. 60, no. C, Elsevier, 1986, pp. 139–46, doi:<a href=\"https://doi.org/10.1016/0012-365X(86)90008-7\">10.1016/0012-365X(86)90008-7</a>.","ieee":"H. Edelsbrunner and D. Haussler, “The complexity of cells in 3-dimensional arrangements,” <i>Discrete Mathematics</i>, vol. 60, no. C. Elsevier, pp. 139–146, 1986."},"article_processing_charge":"No","page":"139 - 146","language":[{"iso":"eng"}],"author":[{"full_name":"Edelsbrunner, Herbert","orcid":"0000-0002-9823-6833","id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","first_name":"Herbert","last_name":"Edelsbrunner"},{"last_name":"Haussler","first_name":"David","full_name":"Haussler, David"}],"month":"06","volume":60,"publication_identifier":{"eissn":["1872-681X"],"issn":["0012-365X"]},"doi":"10.1016/0012-365X(86)90008-7","_id":"4107","oa_version":"None","extern":"1","date_updated":"2022-02-01T12:44:50Z","user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","date_created":"2018-12-11T12:06:59Z","date_published":"1986-06-01T00:00:00Z","status":"public","year":"1986","issue":"C","publisher":"Elsevier","article_type":"original","type":"journal_article"}]