Zobrazeno 1 - 10
of 11
pro vyhledávání: '"Bogdan Alecu"'
Autor:
Bogdan Alecu, Robert Ferguson, Mamadou Moustapha Kanté, Vadim V. Lozin, Vincent Vatter, Victor Zamaraev
Publikováno v:
SIAM Journal on Discrete Mathematics
SIAM Journal on Discrete Mathematics, 2022, 36 (4), pp.2774-2797. ⟨10.1137/21M1449646⟩
SIAM Journal on Discrete Mathematics, 2022, 36 (4), pp.2774-2797. ⟨10.1137/21M1449646⟩
International audience; We uncover a connection between two seemingly unrelated notions: lettericity, from structural graph theory, and geometric griddability, from the world of permutation patterns. Both of these notions capture important structural
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::d11b453c5b495b9f5d920c73f7b195ac
https://doi.org/10.1137/21m1449646
https://doi.org/10.1137/21m1449646
Publikováno v:
Lecture Notes in Computer Science ISBN: 9783030489656
IWOCA
Combinatorial Algorithms
IWOCA
Combinatorial Algorithms
Cographs constitute a small point in the atlas of graph classes. However, by zooming in on this point, we discover a complex world, where many parameters jump from finiteness to infinity. In the present paper, we identify several milestones in the wo
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::8796d8bcfd48b3371ac6fe2388e6e366
Publikováno v:
Lecture Notes in Computer Science ISBN: 9783031066771
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::d4aeba2258b55339cd37ba84f13ae2a8
https://doi.org/10.1007/978-3-031-06678-8_5
https://doi.org/10.1007/978-3-031-06678-8_5
Publikováno v:
Discrete Mathematics
The Ramsey number $R_X(p,q)$ for a class of graphs $X$ is the minimum $n$ such that every graph in $X$ with at least $n$ vertices has either a clique of size $p$ or an independent set of size $q$. We say that Ramsey numbers are linear in $X$ if there
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::79174fbd36c650a896c15591fc5e1dc4
http://wrap.warwick.ac.uk/148196/1/WRAP-graph-classes-linear-Ramsey-numbers-Lozin-2021.pdf
http://wrap.warwick.ac.uk/148196/1/WRAP-graph-classes-linear-Ramsey-numbers-Lozin-2021.pdf
Publikováno v:
Lecture Notes in Computer Science ISBN: 9783030799861
IWOCA
IWOCA
The class of quasi-chain graphs is an extension of the well-studied class of chain graphs. The latter class enjoys many nice and important properties, such as bounded clique-width, implicit representation, well-quasi-ordering by induced subgraphs, et
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::27eaed19e26177229e0e90d04f5d19b5
https://doi.org/10.1007/978-3-030-79987-8_4
https://doi.org/10.1007/978-3-030-79987-8_4
The class of quasi-chain graphs is an extension of the well-studied class of chain graphs. This latter class enjoys many nice and important properties, such as bounded clique-width, implicit representation, well-quasi-ordering by induced subgraphs, e
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::2bd58ff4e9d99fa0afabd68e929a438d
Publikováno v:
Graph-Theoretic Concepts in Computer Science ISBN: 9783030307851
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::619d93bf154d826a29139c45996b52a0
https://doi.org/10.1007/978-3-030-30786-8_11
https://doi.org/10.1007/978-3-030-30786-8_11
Publikováno v:
DISCRETE MATHEMATICS
Discrete Mathematics
Discrete Mathematics, 2020, 343 (8), pp.111926. ⟨10.1016/j.disc.2020.111926⟩
Discrete Mathematics
Discrete Mathematics, 2020, 343 (8), pp.111926. ⟨10.1016/j.disc.2020.111926⟩
International audience; We consider hereditary classes of bipartite graphs where clique-width is bounded, but linear clique-width is not. Our goal is identifying classes that are critical with respect to linear clique-width. We discover four such cla
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::d8ee10933035e9096418d67241f16d82
https://doi.org/10.1016/j.disc.2020.111926
https://doi.org/10.1016/j.disc.2020.111926
Let $G=(V,E)$ be a graph and $A$ its adjacency matrix. We say that a vertex $y \in V$ is a function of vertices $x_1, \ldots, x_k \in V$ if there exists a Boolean function $f$ of $k$ variables such that for any vertex $z \in V - \{y, x_1, \ldots, x_k
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::efc3bac44842b7892142922d2e388d91
http://arxiv.org/abs/1807.01749
http://arxiv.org/abs/1807.01749
Publikováno v:
Lecture Notes in Computer Science ISBN: 9783319946665
IWOCA
IWOCA
We prove that in the class of bi-complement reducible graphs linear clique-width is unbounded and show that this class contains exactly two minimal hereditary subclasses of unbounded linear clique-width.
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::8968ec24f4a094e2050cbe295ca2ce04
https://doi.org/10.1007/978-3-319-94667-2_2
https://doi.org/10.1007/978-3-319-94667-2_2