Zobrazeno 1 - 10
of 145
pro vyhledávání: '"Vadim V. Lozin"'
Publikováno v:
Discrete Mathematics & Theoretical Computer Science, Vol 7, Iss 1 (2005)
The chordality of a graph with at least one cycle is the length of the longest induced cycle in it. The odd (even) chordality is defined to be the length of the longest induced odd (even) cycle in it. Chordal graphs have chordality at most 3. We show
Externí odkaz:
https://doaj.org/article/d8e4029d9534465cb0927f28d49a9468
Publikováno v:
Discrete Mathematics & Theoretical Computer Science, Vol Vol. 7 (2005)
The chordality of a graph with at least one cycle is the length of the longest induced cycle in it. The odd (even) chordality is defined to be the length of the longest induced odd (even) cycle in it. Chordal graphs have chordality at most 3. We show
Externí odkaz:
https://doaj.org/article/e1abd225012a414985f515029e2ca437
Publikováno v:
Discrete Mathematics & Theoretical Computer Science, Vol 6, Iss 2 (2004)
For graph classes ℘ 1,...,℘ k, Generalized Graph Coloring is the problem of deciding whether the vertex set of a given graph G can be partitioned into subsets V 1,...,V k so that V j induces a graph in the class ℘ j (j=1,2,...,k). If ℘ 1 =...
Externí odkaz:
https://doaj.org/article/873b62eabe4b49ebaa23c39ace1597b7
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
Autor:
Vadim V. Lozin, Mikhail Moshkov
In this paper, we define a quasi-order on the set of read-once Boolean functions and show that this is a well-quasi-order. This implies that every parameter measuring complexity of the functions can be characterized by a finite set of minimal subclas
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::88563d34ebcd60c6d789b1ab33041c18
http://wrap.warwick.ac.uk/150345/1/WRAP-critical-properties-complexity-measures-read-once-Boolean-functions-Lozin-2021.pdf
http://wrap.warwick.ac.uk/150345/1/WRAP-critical-properties-complexity-measures-read-once-Boolean-functions-Lozin-2021.pdf
We discover new hereditary classes of graphs that are minimal (with respect to set inclusion) of unbounded clique-width. The new examples include split permutation graphs and bichain graphs. Each of these classes is characterised by a finite list of
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::37d81e0d245b9a866186f1cfff839173
http://oro.open.ac.uk/75508/1/bichain-min-robert.pdf
http://oro.open.ac.uk/75508/1/bichain-min-robert.pdf
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
Publikováno v:
INFORMATION PROCESSING LETTERS
Inf. Process. Lett.
Inf. Process. Lett.
Independent domination is one of the rare problems for which the complexity of weighted and unweighted versions is known to be different in some classes of graphs. Trying to better understand the gap between the two versions of the problem, in the pr
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::3e03fcad6444774898b4a50c89cd20f8
http://livrepository.liverpool.ac.uk/3073237/1/versus-rev-2.pdf
http://livrepository.liverpool.ac.uk/3073237/1/versus-rev-2.pdf