Zobrazeno 1 - 10
of 13
pro vyhledávání: '"Karolina Okrasa"'
Autor:
Marthe Bonamy, Łukasz Bożyk, Andrzej Grzesik, Meike Hatzel, Tomáš Masařík, Jana Novotná, Karolina Okrasa
Publikováno v:
Discrete Mathematics & Theoretical Computer Science, Vol vol. 24, no. 1, Iss Graph Theory (2022)
Tuza famously conjectured in 1981 that in a graph without k+1 edge-disjoint triangles, it suffices to delete at most 2k edges to obtain a triangle-free graph. The conjecture holds for graphs with small treewidth or small maximum average degree, inclu
Externí odkaz:
https://doaj.org/article/b9d6277e33dc42659da823f7cc2d8440
Publikováno v:
Algorithmica. 85:1202-1250
The notion of forbidden-transition graphs allows for a robust generalization of walks in graphs. In a forbidden-transition graph, every pair of edges incident to a common vertex is permitted or forbidden; a walk is compatible if all pairs of consecut
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::c23ec01c30be4d9af35f0993782f8c96
https://doi.org/10.1007/s00453-022-01064-1
https://doi.org/10.1007/s00453-022-01064-1
Autor:
Karolina Okrasa, Paweł Rzążewski
Publikováno v:
Journal of Computer and System Sciences. 109:126-144
We consider the complexity of finding weighted homomorphisms from intersection graphs of curves (string graphs) with n vertices to a fixed graph H. We provide a complete dichotomy for the problem: if H has no two vertices sharing two common neighbors
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::b35479101e4c479b0a6c0f819f16f526
https://doi.org/10.1016/j.jcss.2019.12.004
https://doi.org/10.1016/j.jcss.2019.12.004
Publikováno v:
Graph-Theoretic Concepts in Computer Science-48th International Workshop, WG 2022
Lecture Notes in Computer Science
Lecture Notes in Computer Science-Graph-Theoretic Concepts in Computer Science
Graph-Theoretic Concepts in Computer Science ISBN: 9783031159138
Lecture Notes in Computer Science
Lecture Notes in Computer Science-Graph-Theoretic Concepts in Computer Science
Graph-Theoretic Concepts in Computer Science ISBN: 9783031159138
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::d3e82c06a500cbdff0e04828fdbb09cb
Autor:
Michał Pilipczuk, Erik Jan van Leeuwen, Paweł Rzążewski, Bartosz Walczak, Jana Novotná, Karolina Okrasa
Publikováno v:
Algorithmica, 83, 2634. Springer New York
Algorithmica
Algorithmica
Let $\mathcal{C}$ and $\mathcal{D}$ be hereditary graph classes. Consider the following problem: given a graph $G\in\mathcal{D}$, find a largest, in terms of the number of vertices, induced subgraph of $G$ that belongs to $\mathcal{C}$. We prove that
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::eaed4a6aead840bd1a93db65ab37c1f8
https://dspace.library.uu.nl/handle/1874/415731
https://dspace.library.uu.nl/handle/1874/415731
Publikováno v:
Discrete Applied Mathematics. 267:184-189
A graph is called P t -free if it does not contain the path on t vertices as an induced subgraph. Let H be a multigraph with the property that any two distinct vertices share at most one common neighbour. We show that the generating function for (lis
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::a1828956e412dabf9932c03b217a499b
https://doi.org/10.1016/j.dam.2019.04.010
https://doi.org/10.1016/j.dam.2019.04.010
Publikováno v:
38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=r3c4b2081b22::6fe95ffabf515dd44e5fd3e86e48a77f
Autor:
Karolina Okrasa, Paweł Rzążewski
Publikováno v:
Scopus-Elsevier
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::847fdfc5aa362769c6375d2b0bfae1e5
https://doi.org/10.1137/1.9781611975994.97
https://doi.org/10.1137/1.9781611975994.97
Autor:
Pawel Rzazewski, Karolina Okrasa
Publikováno v:
SIAM Journal on Computing
For graphs $G$ and $H$, a \emph{homomorphism} from $G$ to $H$ is an edge-preserving mapping from the vertex set of $G$ to the vertex set of $H$. For a fixed graph $H$, by \textsc{Hom($H$)} we denote the computational problem which asks whether a give
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::758827bd25bbd7bac245fba5aae2f08b
Autor:
Pawel Rzazewski, Karolina Okrasa
Publikováno v:
Graph-Theoretic Concepts in Computer Science ISBN: 9783030307851
WG
WG
We consider the complexity of finding weighted homomorphisms from intersection graphs of curves (string graphs) with n vertices to a fixed graph H. We provide a complete dichotomy for the problem: if H has no two vertices sharing two common neighbors
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::084ef96f58126fb85b4866288ff718ab
https://doi.org/10.1007/978-3-030-30786-8_1
https://doi.org/10.1007/978-3-030-30786-8_1