Skip to main content Skip to navigation

Mathematics Institute

Vadim Lozin's publication list

in back chronological order

Books

  1. Words and Graphs
    Sergey Kitaev and Vadim Lozin
    Springer, 264 pp. 2015
    ISBN 978-3-319-25857-7
  1. Surveys in Combinatorics,
    A. Czumaj, A. Georgakopoulos, D. Kral, V. Lozin, O. Pikhurko (Editors)
    Cambridge University Press, 334 pp. 2015
    ISBN 9781107462502
  1. Three approaches to data analysis,
    I. Chikalov, V. Lozin, I. Lozina, M. Moshkov, H.S. Nguyen, A. Skowron, B. Zielosko
    Springer, 202 pp. 2013
    ISBN 978-3-642-28666-7

Refereed journal articles and conference proceedings

2024

  1. Union-closed sets and Horn Boolean functions
    Vadim Lozin, Viktor Zamaraev
    J. Combinatorial Theory A, 202 (2024) 105818.
    DOI: 10.1016/j.jcta.2023.105818
  1. Deciding atomicity of subword-closed languages
    Aistis Atminas, Vadim Lozin
    Theoretical Computer Science, 1003 (2024) 114595.
    DOI: 10.1016/j.tcs.2024.114595
  1. The treewidth and pathwidth of graph unions
    B. Alecu, V. Lozin, D. A. Quiroz, R. Rabinovich, I. Razgon, V. Zamaraev
    SIAM J. Discrete Mathematics, 38 (2024) 261-276.
    DOI: 10.1137/22M1524047
  1. Ramsey numbers and graph parameters
    Vadim Lozin,
    Graphs and Combinatorics, 40 (2024) 29.
    DOI: 10.1007/s00373-024-02755-y
  1. Functionality of box intersection graphs
    C. Dallard, V. Lozin, M. Milanic, K. Storgel, V. Zamaraev
    Results in Mathematics, 79 (2024) 48.
    DOI: 10.1007/s00025-023-02075-2
  1. Critical properties of bipartite permutation graphs
    Bogdan Alecu, Vadim Lozin, Dmitriy Malyshev
    J. Graph Theory, 105 (2024) 34-60.
    DOI: 10.1002/jgt.23011
  1. The Hamiltonian cycle problem and monotone classes
    Vadim Lozin
    Lecture Notes in Computer Science, 14764 (2024) 460-471.
    DOI: 10.1007/978-3-031-63021-7_35

2023

  1. Hereditary classes of graphs: a parametric approach
    Vadim Lozin
    Discrete Applied Mathematics, 325 (2023) 134-151.
    DOI: 10.1016/j.dam.2022.10.016
  1. Graph parameters, implicit representations and factorial properties
    Bogdan Alecu, Vladimir E. Alekseev, Aistis Atminas, Vadim Lozin, Viktor Zamaraev
    Discrete Mathematics, 346 (2023) 113573.
    DOI: 10.1016/j.disc.2023.113573
  1. Combinatorics and algorithms for quasi-chain graphs
    Bogdan Alecu, Aistis Atminas, Vadim Lozin, Dmitriy Malyshev
    Algorithmica, 85 (2023) 642–664.
    DOI: 10.1007/s00453-022-01019-6

2022

  1. On Boolean threshold functions with minimum specification number
    Vadim Lozin, Viktor Zamaraev, Elena Zamaraeva, Nikolai Yu. Zolotykh
    Information and Computation, 289 (2022) 104926.
    DOI: 10.1016/j.ic.2022.104926
  1. Letter graphs and geometric grid classes of permutations
    Bogdan Alecu, Robert Ferguson, Mamadou Moustapha Kanté, Vadim Lozin, Vincent Vatter, Viktor Zamaraev
    SIAM J. Discrete Math., 36 (2022) 2774-2797.
    DOI: 10.1137/21M1449646
  1. Tree-width dichotomy
    V. Lozin, I. Razgon
    European J. Combinatorics, 103 (2022) 103517.
    DOI: 10.1016/j.ejc.2022.103517
  1. The micro-world of cographs
    B. Alecu, V. Lozin, D. de Werra
    Discrete Applied Mathematics, 312 (2022) 3-14.
    DOI: 10.1016/j.dam.2021.11.004
  1. Graph parameters, implicit representations and factorial properties
    Bogdan Alecu, Vladimir E. Alekseev, Aistis Atminas, Vadim Lozin, Viktor Zamaraev
    Lecture Notes in Computer Science, 13270 (2022) 60-72.
    DOI: 10.1007/978-3-031-06678-8_5
  1. Deciding atomicity of subword-closed languages
    Aistis Atminas, Vadim Lozin
    Lecture Notes in Computer Science, 13257 (2022) 69-77.
    DOI: 10.1007/978-3-031-05578-2_5

2021

  1. Critical properties and complexity measures of read-once Boolean functions
    Vadim Lozin, Mikhail Moshkov
    Annals of Mathematics and Artificial Intelligence, 89 (2021) 595-614.
    DOI: 10.1007/s10472-021-09734-6
  1. Cliques, Colouring and Satisfiability: From Structure to Algorithms
    Vadim Lozin
    Topics in algorithmic graph theory, 105-129
    Encyclopedia Math. Appl., 178 Cambridge Univ. Press, Cambridge, 2021
    ISBN 9781108492607
  1. Graph Functionality
    Bogdan Alecu, Aistis Atminas, Vadim Lozin
    J. Combinatorial Theory B, 147 (2021) 139-158.
    DOI: 10.1016/j.jctb.2020.11.002
  1. Minimal classes of graphs of unbounded clique-width defined by finitely many forbidden induced subgraphs
    A. Atminas, R, Brignall, V. Lozin, J. Stacho
    Discrete Applied Mathematics, 295 (2021) 57-69.
    DOI: 10.1016/j.dam.2021.02.007
  1. Graph classes with linear Ramsey numbers
    Bogdan Alecu, Aistis Atminas, Vadim Lozin, Viktor Zamaraev
    Discrete Mathematics, 344 (2021) 112307.
    DOI: 10.1016/j.disc.2021.112307
  1. Combinatorics and algorithms for quasi-chain graphs
    Bogdan Alecu, Aistis Atminas, Vadim Lozin, Dmitriy Malyshev
    Lecture Notes in Computer Science, 12757 (2021) 49-62.
    DOI: 10.1007/978-3-030-79987-8_4

2020

  1. Letter graphs and geometric grid classes of permutations : characterization and recognition
    B. Alecu, V. Lozin, D. de Werra, V. Zamaraev
    Discrete Applied Mathematics, 283 (2020) 482-494.
    DOI: 10.1016/j.dam.2020.01.038
  1. Clique-width for graph classes closed under complementation
    A. Blanché, K. Dabrowski, M. Johnson, V. Lozin, D. Paulusma, V. Zamaraev
    SIAM Journal on Discrete Mathematics, 34 (2020) 1107–1147.
    DOI: 10.1137/18M1235016
  1. The micro-world of cographs
    B. Alecu, V. Lozin, D. de Werra
    Lecture Notes in Computer Science, 12126 (2020) 30-42.
    DOI: 10.1007/978-3-030-48966-3_3
  1. Between clique-width and linear clique-width of bipartite graphs
    B. Alecu, M.M. Kanté, V. Lozin, V. Zamaraev
    Discrete Mathematics, 343 (2020) 111926.
    DOI: 10.1016/j.disc.2020.111926
  1. Independent domination versus weighted independent domination
    V. Lozin, D. Malyshev, R. Mosca, V. Zamaraev
    Information Processing Letters, 156 (2020) 105914.
    DOI: 10.1016/j.ipl.2020.105914
  1. Maximum independent sets in subcubic graphs: new results.
    A. Harutyunyan, M. Lampis, V. Lozin, J. Monnot:
    Theoretical Computer Science, 846 (2020) 14-26.
    DOI: 10.1016/j.tcs.2020.09.010
  1. Clique-width and well-quasi-ordering of triangle-free graph classes
    K.Dabrowski, V.Lozin, D. Paulusma
    Journal of Computer and System Sciences, 108 (2020) 64-91.
    DOI: 10.1016/j.jcss.2019.09.001

2019

  1. Graphs without large bicliques and well-quasi-orderability by the induced subgraph relation
    Aistis Atminas, Vadim Lozin, Igor Razgon
    Journal of Combinatorics, 10 (2019) 327-337.
    DOI: 10.4310/JOC.2019.v10.n2.a8
  1. Recent advances in the theory and practice of Logical Analysis of Data
    Miguel Lejeune, Vadim Lozin, Irina Lozina, Ahmed Ragab, Soumaya Yacout
    European Journal of Operational Research, 275 (2019) 1-15.
    DOI: 10.1016/j.ejor.2018.06.011
  1. From words to graphs, and back
    Vadim Lozin
    Lecture Notes in Computer Science, 11417 (2019) 43-54.
    DOI: 10.1007/978-3-030-13435-8_3
  1. Maximum Independent Sets in Subcubic Graphs: New Results.
    A. Harutyunyan, M. Lampis, V. Lozin, J. Monnot:
    Lecture Notes in Computer Science, 11789 (2019) 40-52.
    DOI: 10.1007/978-3-030-30786-8_4
  1. Graph Functionality
    Bogdan Alecu, Aistis Atminas, Vadim V. Lozin
    Lecture Notes in Computer Science, 11789 (2019) 135-147.
    DOI: 10.1007/978-3-030-30786-8_11

2018

  1. Well-quasi-ordering versus clique-width
    V. Lozin, I. Razgon, V. Zamaraev
    J. Combinatorial Theory B, 130 (2018) 1-18.
    DOI: 10.1016/j.jctb.2017.09.012
  1. Linear read-once and related Boolean functions
    Vadim Lozin, Igor Razgon, Viktor Zamaraev, Elena Zamaraeva, Nikolai Zolotykh
    Discrete Applied Mathematics, 250 (2018) 16-27.
    DOI: 10.1016/j.dam.2018.05.001
  1. Upper Domination: Towards a Dichotomy Through Boundary Properties
    Hassan AbouEisha, Shahid Hussain, Vadim Lozin, Jérôme Monnot, Bernard Ries, Viktor Zamaraev
    Algorithmica, 80 (2018) 2799-2917.
    DOI: 10.1007/s00453-017-0346-9
  1. Well-quasi-ordering versus clique-width: new results on bigenic classes
    Konrad Dabrowski, Vadim Lozin, Daniël Paulusma
    Order, 35 (2018) 253-274.
    DOI: 10.1007/s11083-017-9430-7
  1. Perfect Edge Domination: Hard and Solvable Cases
    Min Chih Lin, Vadim Lozin, Veronica A. Moyano, Jayme L. Szwarcfiter
    Annals of Operations Research, 264 (2018) 287-305.
    DOI: 10.1007/s10479-017-2664-3
  1. Dominating induced matchings in graphs containing no long claw
    A. Hertz, V. Lozin, B. Ries, V. Zamaraev, D. de Werra
    J. Graph Theory, 88 (2018) 18-39.
    DOI: 10.1002/jgt.22182
  1. Infinitely many minimal classes of graphs of unbounded clique-width,
    A. Collins, J. Foniok, N. Korpelainen, V. Lozin, V. Zamaraev
    Discrete Applied Mathematics, 248 (2018) 145-152.
    DOI: 10.1016/j.dam.2017.02.012
  1. Linear Ramsey numbers
    Aistis Atminas, Vadim Lozin, Viktor Zamaraev
    Lecture Notes in Computer Science, 10979 (2018) 26-38.
    DOI: 10.1007/978-3-319-94667-2_3
  1. Linear clique-width of of bi-complement reducible graphs
    Bogdan Alecu, Vadim Lozin, Viktor Zamaraev
    Lecture Notes in Computer Science, 10979 (2018) 14-25.
    DOI: 10.1007/978-3-319-94667-2_2
  1. Letter Graphs and Geometric Grid Classes of Permutations: Characterization and Recognition
    Bogdan Alecu, Vadim Lozin, Viktor Zamaraev, Dominique de Werra
    Lecture Notes in Computer Science, 10765 (2018) 195-205.
    DOI: 10.1007/978-3-319-78825-8_16
  1. Graph Parameters and Ramsey Theory
    Vadim Lozin
    Lecture Notes in Computer Science, 10765 (2018) 185-194.
    DOI: 10.1007/978-3-319-78825-8_15

2017

  1. WQO is decidable for factorial languages,
    A. Atminas, V. Lozin, M. Moshkov
    Information and Computation, 256 (2017) 321-333.
    DOI: 10.1016/j.ic.2017.08.001
  1. The structure and the number of P7-free bipartite graphs,
    V. Lozin, V. Zamaraev
    European J. Combinatorics, 65 (2017) 143-153.
    DOI: 10.1016/j.ejc.2017.05.008
  1. More results on weighted independent domination
    V. Lozin, D. Malyshev, R. Mosca, V. Zamaraev
    Theoretical Computer Science, 700 (2017) 63-74.
    DOI: 10.1016/j.tcs.2017.08.007
  1. From matchings to independent sets,
    Vadim Lozin
    Discrete Applied Mathematics, 231 (2017) 4-14.
    DOI: 10.1016/j.dam.2016.04.012
  1. New results on word-representable graphs,
    Andrew Collins, Sergey Kitaev and Vadim Lozin
    Discrete Applied Mathematics, 216 (2017) 136-141.
    DOI: 10.1016/j.dam.2014.10.024
  1. Vertex coloring of graphs with few obstructions
    V. Lozin and D.S. Malyshev
    Discrete Applied Mathematics, 216 (2017) 273-280.
    DOI: 10.1016/j.dam.2015.02.015
  1. Specifying a positive threshold function via extremal points
    Vadim Lozin, Igor Razgon, Viktor Zamaraev, Elena Zamaraeva, Nikolai Zolotykh
    Proceedings of the 28th International Conference on Algorithmic Learning Theory (ALT 2017)
    Proceedings of Machine Learning Research, 76 (2017) 208-222.
    Electronic edition
  1. Clique-width for graph classes closed under complementation
    A. Blanche, K.K. Dabrowski, M. Johnson, V.V. Lozin, D. Paulusma and V. Zamaraev
    Proceedings of the 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)
    Leibniz International Proceedings in Informatics, 83 (2017) 73:1-73:14.
    DOI: 10.4230/LIPIcs.MFCS.2017.73
  1. New results on weighted independent domination
    V. Lozin, D. Malyshev, R. Mosca, V. Zamaraev
    Lecture Notes in Computer Science, 10520 (2017) 399-411.
    DOI: 10.1007/978-3-319-68705-6_30
  1. Clique-width and well-quasi-ordering of triangle-Free graph classes
    Konrad Dabrowski, Vadim Lozin, Daniël Paulusma
    Lecture Notes in Computer Science, 10520 (2017) 220-233.
    DOI: 10.1007/978-3-319-68705-6_17

2016

  1. Deciding the Bell number for hereditary graph properties,
    A. Atminas, A. Collins, J. Foniok, and V. Lozin
    SIAM J. Discrete Mathematics, 30 (2016) 1015–1031.
    DOI: 10.1137/15M1024214
  1. Combinatorics and algorithms for augmenting graphs,
    Konrad Dabrowski, Vadim Lozin, Dominique de Werra, Viktor Zamaraev
    Graphs and Combinatorics, 32 (2016) 1339–1352.
    DOI: 10.1007/s00373-015-1660-0
  1. Efficient domination through eigenvalues,
    D.M. Cardoso, V.V. Lozin, C.J. Luz, M.F. Pacheco
    Discrete Applied Mathematics, 214 (2016) 54-62.
    DOI: 10.1016/j.dam.2016.06.014
  1. Well-quasi-ordering versus clique-width: new results on bigenic classes
    Konrad Dabrowski, Vadim Lozin, Daniël Paulusma
    Lecture Notes in Computer Science, 9843 (2016) 253-265.
    DOI: 10.1007/978-3-319-44543-4_20
  1. A boundary property for upper domination
    Hassan AbouEisha, Shahid Hussain, Vadim Lozin, Jérôme Monnot, Bernard Ries, Viktor Zamaraev
    Lecture Notes in Computer Science, 9843 (2016) 229-240.
    DOI: 10.1007/978-3-319-44543-4_18
  1. Well-quasi-ordering does not imply bounded clique-width,
    Vadim Lozin, Igor Razgon, Viktor Zamaraev
    Lecture Notes in Computer Science, 9224 (2016) 351-359.
    DOI: 10.1007/978-3-662-53174-7_25
  1. Bichain graphs: geomeric model and universal graphs,
    Robert Brignall, Vadim Lozin, and Juraj Stacho
    Discrete Applied Mathematics, 199 (2016) 16-29.
    DOI: 10.1016/j.dam.2014.08.031

2015

  1. Labelled induced subgraphs and well-quasi-ordering,
    Aistis Atminas and Vadim Lozin
    Order, 32 (2015) 313-328.
    DOI: 10.1007/s11083-014-9333-9
  1. Well-quasi-order for permutation graphs omitting a path and a clique,
    Aistis Atminas, Robert Brignall, Nicholas Korpelainen, Vadim Lozin, Vincent Vatter
    Electronic J. Combinatorics, 22 (2015) P2.20
    File
  1. Boundary properties of factorial classes of graphs,
    V. Lozin and V. Zamaraev
    J. Graph Theory, 78 (2015) 207-218.
    DOI: 10.1002/jgt.21799
  1. Implicit representations and factorial properties of graphs,
    Aistis Atminas, Andrew Collins, Vadim Lozin, and Viktor Zamaraev
    Discrete Mathematics, 338 (2015) 164-179.
    DOI: 10.1016/j.disc.2014.09.008
  1. On the maximum independent set problem in subclasses of subcubic graphs,
    Vadim Lozin, Jérôme Monnot and Bernard Ries
    J. Discrete Algorithms, 31 (2015) 104-112.
    DOI: 10.1016/j.jda.2014.08.005
  1. Independent domination in finitely defined classes of graphs: polynomial algorithms,
    Vadim Lozin, Raffaele Mosca and Christopher Purcell
    Discrete Applied Mathematics, 182 (2015) 2-14.
    DOI: 10.1016/j.dam.2013.08.030
  1. Stable-P Partitions of Graphs,
    Konrad K. Dabrowski, Vadim V. Lozin, and Juraj Stacho
    Discrete Applied Mathematics, 182 (2015) 104-114.
    DOI: 10.1016/j.dam.2013.07.001

2014

  1. Deciding the Bell number for hereditary graph properties,
    A. Atminas, A. Collins, J. Foniok, and Vadim V. Lozin
    Lecture Notes in Computer Science, 8747 (2014) 69-80.
    DOI: 10.1007/978-3-319-12340-0_6
  1. Coloring vertices of claw-free graphs in three colors,
    V.V. Lozin, and C. Purcell
    J. Combinatorial Optimization, 28 (2014) 462-479.
    DOI: 10.1007/s10878-012-9577-5
  1. Dominating induced matchings in graphs without a skew star,
    Nicholas Korpelainen, Vadim V. Lozin and Christopher Purcell
    J. Discrete Algorithms, 26 (2014) 45-55.
    DOI: 10.1016/j.jda.2013.11.002
  1. A dichotomy for upper domination in monogenic classes,
    H. AbouEisha, S. Hussain, V. Lozin, J. Monnot, B. Ries,
    Lecture Notes in Computer Science, 8881 (2014) 258-267.
    DOI: 10.1007/978-3-319-12691-3_20
  1. Split permutation graphs,
    N. Korpelainen, V.V. Lozin, and C. Mayhill
    Graphs and Combinatorics, 30 (2014) 633-646.
    DOI: 10.1007/s00373-013-1290-3
  1. Graphs without large apples and the maximum weight independent set problem,
    V.V. Lozin, M. Milanic and C. Purcell
    Graphs and Combinatorics, 30 (2014) 395-410.
    DOI: 10.1007/s00373-012-1263-y

2013

  1. Sparse regular induced subgraphs in 2P3-free graphs,
    Vadim V. Lozin, Raffaele Mosca and Christopher Purcell
    Discrete Optimization, 10 (2013) 304-309.
    DOI: 10.1016/j.disopt.2013.08.001
  1. Universal graphs and universal permutations,
    Aistis Atminas, Sergey Kitaev, Vadim V. Lozin, and Alexandr Valyuzhenic
    Discrete Mathematics, Algorithms and Applications, 5 (2013) 15 pages.
    DOI: 10.1142/S1793830913500389
  1. On the maximum independent set problem in subclasses of subcubic graphs,
    Vadim Lozin Jérôme Monnot and Bernard Ries
    Lecture Notes in Computer Science, 8288 (2013) 314-326.
    DOI: 10.1007/978-3-642-45278-9_27
  1. Boundary properties of well-quasi-ordered sets of graphs,
    N. Korpelainen, V.V. Lozin, and I. Razgon
    Order, 30 (2013) 723-735.
    DOI: 10.1007/s11083-012-9272-2
  1. Deciding WQO for factorial languages,
    A. Atminas, V.V. Lozin, and M. Moshkov
    Lecture Notes in Computer Science, 7810 (2013) 68-79.
    DOI: 10.1007/978-3-642-37064-9_8
  1. New Results on Maximum Induced Matchings in Bipartite Graphs and Beyond
    K. Dabrowski, M. Demange, V.V. Lozin
    Theoretical Computer Science, 478 (2013) 33-40.
    DOI: 10.1016/j.tcs.2013.01.027
  1. Boundary properties of the satisfiability problems
    V.V. Lozin, and C. Purcell
    Information Processing Letters, 113 (2013) 313–317.
    DOI: 10.1016/j.ipl.2013.01.022
  1. Critical properties of graphs of bounded clique-width
    V.V. Lozin, and M. Milanic
    Discrete Mathematics, 313 (2013) 1035–1044.
    DOI: 10.1016/j.disc.2013.01.008

2012

  1. Maximum regular induced subgraphs in 2P3-free graphs,
    V.V. Lozin, and R. Mosca
    Theoretical Computer Science, 460 (2012) 26-33.
    DOI: 10.1016/j.tcs.2012.06.014
  1. On factorial properties of chordal bipartite graphs,
    K. Dabrowski, V.V. Lozin, and V. Zamaraev
    Discrete Mathematics, 312 (2012) 2457-2465.
    DOI: 10.1016/j.disc.2012.04.010
  1. Linear time algorithm for computing a small biclique in graphs without long induced paths,
    A. Atminas, V.V. Lozin, and I. Razgon,
    Lecture Notes in Computer Science, 7357 (2012) 142-152.
    DOI: 10.1007/978-3-642-31155-0_13
  1. Parameterized Complexity of the Weighted Independent Set Problem beyond Graphs of Bounded Clique Number,
    K. Dabrowski, V.V. Lozin, H. Müller and D. Rautenbach
    Journal of Discrete Algorithms, 14 (2012) 207-213.
    DOI: 10.1016/j.jda.2011.12.012
  1. Colouring vertices of triangle-free graphs without forests,
    K. Dabrowski, V.V. Lozin, R. Raman and B. Ries
    Discrete Mathematics, 312 (2012) 1372-1385.
    DOI: 10.1016/j.disc.2011.12.012
  1. On hereditary properties of the class of graphs with convex quadratic stability number
    D. Cardoso, and V.V. Lozin
    Journal of Mathematical Sciences, 182 (2012) 227-232.
    DOI: 10.1007/s10958-012-0743-1
  1. Locally bounded coverings and factorial properties of graphs,
    V.V. Lozin, C. Mayhill and V. Zamaraev
    European J. Combinatorics, 33 (2012) 534–543.
    DOI: 10.1016/j.ejc.2011.10.006

2011

  1. Minimal classes of graphs of unbounded clique-width,
    V.V. Lozin
    Annals of Combinatorics, 15 (2011) 707-722.

  1. Stability preserving transformations of graphs,
    V.V. Lozin
    Annals of Operations Research, 188 (2011) 331-341.
    Preprint

  1. Canonical antichains of unit interval and bipartite permutation graphs,
    V.V. Lozin and C. Mayhill
    Order, 28 (2011) 513-522.

  1. A note on the speed of hereditary graph properties,
    V.V. Lozin, C. Mayhill and V. Zamaraev
    Electronic Journal of Combinatorics, 18 (2011) Research Paper 157.
    File

  1. Bipartite Induced Subgraphs and Well-Quasi-Ordering
    N. Korpelainen, and V.V. Lozin
    Journal of Graph Theory, 67 (2011) 235-249.

  1. Two forbidden induced subgraphs and well-quasi-ordering,
    N. Korpelainen, and V.V. Lozin
    Discrete Mathematics, 311 (2011) 1813-1822.

  1. Boundary Properties of Graphs for Algorithmic Graph Problems,
    N. Korpelainen, V. V. Lozin, D. S. Malyshev and A. Tiskin
    Theoretical Computer Science, 412 (2011) 3545-3554.

  1. On the complexity of the dominating induced matching problem in hereditary classes of graphs
    D. Cardoso, N. Korpelainen, and V.V. Lozin
    Discrete Applied Mathematics, 159 (2011) 521-531.

2010

  1. A decidability result for the dominating set problem
    V.V. Lozin
    Theoretical Computer Science, 411 (2010) 4023-4027.

  1. Independent sets of maximum weight in apple-free graphs
    A. Brandstädt, V.V. Lozin and R. Mosca
    SIAM J. Discrete Mathematics, 24 (2010) 239-254.

  1. Colouring vertices of triangle-free graphs,
    K. Dabrowski, V.V. Lozin, R. Raman and B. Ries,
    Lecture Notes in Computer Science, 6410 (2010) 184-195.

  1. Parameterized Algorithms for the Independent Set Problem in Hereditary Graph Classes,
    K. Dabrowski, V.V. Lozin, H. Müller and D. Rautenbach,
    Lecture Notes in Computer Science, 6460 (2010) 1-9.

  1. Hamiltonian cycles in subcubic graphs: what makes the problem difficult
    N. Korpelainen, V.V. Lozin and A. Tiskin,
    Lecture Notes in Computer Science, 6108 (2010) 320-327.

  1. On the maximum independent set problem in subclasses of planar graphs,
    V.V. Lozin and M. Milanic
    Journal of Graph Algorithms and Applications, 14 (2010) 269-286.

  1. Deciding k-colorability of P5-free graphs in polynomial time
    C. Hoang, M. Kaminski, V. Lozin, J. Sawada, and X. Shu
    Algorithmica, 57 (2010) 74-81.
    Preprint

  1. On independent vertex sets in subclasses of apple-free graphs
    A. Brandstädt, T. Klembt, V.V. Lozin and R. Mosca
    Algorithmica, 56 (2010) 383-393.

2009

  1. Bipartite graphs of large clique-width
    N. Korpelainen, V. Lozin
    Lecture Notes in Computer Science, 5874 (2009) 385-395.

  1. Recent developments on graphs of bounded clique-width
    M. Kaminski, V.V. Lozin and M. Milanic
    Discrete Applied Mathematics, 157 (2009) 2747-2761.
    Preprint

  1. Parameterized complexity of the maximum independent set problem and the speed of hereditary properties
    V.V. Lozin
    Electronic Notes in Discrete Mathematics, 34 (2009) 127-131.

  1. Dominating induced matchings
    D.M. Cardoso and V.V. Lozin
    Lecture Notes in Computer Science, 5420 (2009) 77-86.

  1. Clique-width and the speed of hereditary properties
    Peter Allen, V.V. Lozin and M. Rao
    Electronic Journal of Combinatorics, 16 (2009) Research Paper 35.
    PDF File

  1. Maximum independent sets in subclasses of P5-free graphs
    V.V. Lozin and R. Mosca
    Information Processing Letters, 109 (2009) 319-324.

2008

  1. A polynomial algorithm to find an independent set of maximum weight in a fork-free graph
    V.V. Lozin and Martin Milanic
    Journal of Discrete Algorithms, 6 (2008) 595-604.
    Preprint

  1. Graph representation functions computable by finite automata
    V.V. Lozin
    Journal of Automata, Languages and Combinatorics, 13 (2008) 73-90.
    Preprint

  1. The clique-width of bipartite graphs in monogenic classes
    V.V. Lozin and J. Volz
    International Journal of Foundations of Computer Science, 19 (2008) 477-494.
    Preprint

  1. Gearing Optimization
    V.V. Lozin
    Optimization and Engineering, 9 (2008) 201-211.
    Preprint The original publication is available at www.springerlink.com.

  1. Boundary classes of planar graphs
    V.V. Lozin
    Combinatorics, Probability and Computing, 17 (2008) 287-295.
    Preprint

  1. On Finding Augmenting Graphs
    V.V. Lozin and M. Milanic
    Discrete Applied Mathematics, 156 (2008) 2517-2529.
    Preprint

  1. A note on k-colorability of P5-free graphs
    C. Hoang, M. Kaminski, V. Lozin, J. Sawada, and X. Shu
    Lecture Notes in Computer Science, 5162 (2008) 387-394.

  1. The maximum independent set problem in planar graphs
    Vladimir E. Alekseev, Vadim Lozin, Dmitriy Malyshev, and Martin Milanic
    Lecture Notes in Computer Science, 5162 (2008) 96-107.

  1. Independent sets of maximum weight in apple-free graphs
    A. Brandstädt, T. Klembt, V.V. Lozin and R. Mosca
    Lecture Notes in Computer Science 5369 (2008) 849-859

  1. From tree-width to clique-width: excluding a unit interval graph
    V.V. Lozin
    Lecture Notes in Computer Science 5369 (2008) 872-883

2007

  1. NP-hard Graph problems and Boundary Classes of Graphs
    V.E. Alekseev, R. Boliac, D.V. Korobitsyn and V.V. Lozin
    Theoretical Computer Science, 389 (2007) 219-236.
    Preprint

  1. Maximum k-regular induced subgraphs
    D. Cardoso, M. Kaminski and V.V. Lozin
    Journal of Combinatorial Optimization, 14 (2007) 455-463.
    Preprint 

  1. The Relative Clique-Width of a Graph
    V.V. Lozin and D. Rautenbach
    Journal of Combinatorial Theory B, 95 (2007) 846-858.
    Preprint 

  1. Vertex 3-colorability of claw-free graphs
    M. Kaminski and V.V. Lozin
    Algorithmic Operations Research, 2 (2007) 15-21.
    Preprint

  1. Coloring edges and vertices of graphs without short or long cycles
    M. Kaminski and V.V. Lozin
    Contributions to Discrete Mathematics, 2 (2007) 61-66.
    Preprint

  1. Minimal Universal Bipartite Graphs
    V.V. Lozin and Gabor Rudolf
    Ars Combinatoria, 84 (2007) 345-356.
    Preprint 

  1. Maximum Independent Sets in Graphs of Low Degree
    V.V. Lozin and Martin Milanic
    Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (2007) 874-880.

  1. Treewidth and Optimization in Bounded Degree Graphs
    V.V. Lozin and M. Milanic
    Lecture Notes in Computer Science, 4769 (2007) 45-54.

2006

  1. Clique-Width for Four-Vertex Forbidden Subgraphs
    A. Brandstädt, J. Engelfriet, Hoang-Oanh Le and V.V. Lozin
    Theory of Computing Systems, 34 (2006) 561-590.
    Extended abstract appeared in [34].
    Preprint 

  1. Augmenting chains in graphs without a skew star
    M.U. Gerber, A. Hertz and V.V. Lozin
    Journal of Combinatorial Theory, B, 96 (2006) 352-366.
    Preprint 

  1. Polar Graphs and Maximal Independent Sets
    V.V. Lozin and R. Mosca
    Discrete Mathematics, 306 (2006) 2901-2908.
    Preprint

  1. The Tree- and Clique-width of Bipartite Graphs in Special Classes
    V.V. Lozin and Dieter Rautenbach
    Australasian Journal of Combinatorics, 34 (2006) 57-67.
    Preprint 

  1. A Polynomial Algorithm to Find an Independent Set of Maximum Weight in a Fork-free Graph (Extended abstract)
    V.V. Lozin and Martin Milanic
    Proceedings of the ACM-SIAM Symposium on Discrete Algorithms SODA'06, (2006) 26-30.
    Preprint 

2005

  1. Bisplit Graphs
    A. Brandstädt, Peter L. Hammer, Van Bang Le and V.V. Lozin
    Discrete Mathematics, 299 (2005) 11-32.
    Preprint 

  1. Graphs of low chordality
    L.S. Chandran, V.V. Lozin and C.R. Subramanian
    Discrete Mathematics and Theoretical Computer Science, 7 (2005) 25-36.
    Preprint 

  1. Independent Sets in Extensions of 2K2-free Graphs
    V.V. Lozin and R. Mosca
    Discrete Applied Mathematics, 146 (2005) 74-80.
    Preprint 

  1. Between 2- and 3-colorability
    V.V. Lozin
    Information Processing Letters, 94 (2005) 179-182.
    Preprint

  1. Clique-Width for Four-Vertex Forbidden Subgraphs (Extended abstract)
    A. Brandstädt, J. Engelfriet, Hoang-Oanh Le and V.V. Lozin
    Lecture Notes in Computer Science, 3623 (2005) 185-196.

  1. The Maximum Independent Set Problem and Augmenting Graphs
    A. Hertz and V.V. Lozin
    "Graph Theory and Combinatorial Optimization" Springer, 2005, 69-99.
    Preprint 

2004

  1. Augmenting graphs for independent sets
    V.E. Alekseev and V.V. Lozin
    Discrete Applied Mathematics, 145 (2004) 3-10.
    Preprint 

  1. Boundary classes of graphs for the dominating set problem
    V.E. Alekseev, D.V. Korobitsyn and V.V. Lozin
    Discrete Mathematics, 285 (2004) 1-6.
    Preprint 

  1. On the band-, tree- and clique-width of graphs with bounded vertex degree
    V.V. Lozin and Dieter Rautenbach
    SIAM J. Discrete Math., 18 (2004) 195-206.
    Preprint 

  1. On computing the dissociation number of bipartite graphs
    R. Boliac, K. Cameron and V.V. Lozin
    Ars Combinatoria, 72 (2004) 241-253.
    Preprint 

  1. Chordal bipartite graphs of bounded tree- and clique-width
    V.V. Lozin and Dieter Rautenbach
    Discrete Mathematics, 283 (2004) 151-158.
    Preprint 

  1. New results on generalized graph coloring
    V.E. Alekseev, A. Farrugia and V.V. Lozin
    Discrete Mathematics and Theoretical Computer Science, 6 (2004) 215-222.
    Preprint 

  1. Local transformations of graphs preserving independence number
    V.E. Alekseev and V.V. Lozin
    Discrete Applied Mathematics, 135 (2004) 16-29.
    Abstract

  1. Struction Revisited
    G. Alexe, Peter L. Hammer, V.V. Lozin and Dominique de Werra
    Discrete Applied Mathematics, 132 (2004) 27-46.
    Preprint 

  1. Stable sets in two subclasses of banner-free graphs
    M.U. Gerber, A. Hertz and V.V. Lozin
    Discrete Applied Mathematics, 132 (2004) 121-136 .
    Preprint 

2003

  1. Some results on graphs without long induced paths
    V.V. Lozin and Dieter Rautenbach
    Information Processing Letters, 88 (2003) 167-171.
    Preprint 

  1. An augmenting graph approach to the stable set problem in P5-free graphs
    R. Boliac and V.V. Lozin
    Discrete Applied Mathematics 131 (2003) 567-575.
    Preprint 

  1. Robust algorithms for the stable set problem
    M.U. Gerber and V.V. Lozin
    Graphs and Combinatorics, 19 (2003) 347-356.
    Preprint 

  1. The 3-colorability problem on graphs with maximum degree four
    Martin Kochol, V.V. Lozin and Bert Randerath
    SIAM J. Computing, 32 (2003) 1128-1139.
    Preprint 

  1. Independent domination in finitely defined classes of graphs
    R. Boliac and V.V. Lozin
    Theoretical Computer Science 301 (2003) 271-284.
    Preprint 

  1. Finding augmenting chains in extensions of claw-free graphs
    A. Hertz, V.V. Lozin and D. Schindl
    Information Processing Letters 86 (2003) 311-316.
    Preprint

  1. On the linear structure and clique-width of bipartite permutation graphs
    A. Brandstädt and V.V. Lozin
    Ars Combinatoria 67 (2003) 273-281.
    Preprint

  1. Independent sets of maximum weight in (p,q)-colorable graphs
    V.E. Alekseev and V.V. Lozin
    Discrete Mathematics 265 (2003) 351-356.
    Preprint 

  1. On the stable set problem in special P5-free graphs
    M.U. Gerber and V.V. Lozin
    Discrete Applied Mathematics 125 (2003) 215-224.
    Preprint 

2002

  1. On the clique-width of graphs in hereditary classes
    R. Boliac and V.V. Lozin
    Lecture Notes in Computer Science 2518 (2002) 44-54.
    Preprint 

  1. Bipartite graphs without a skew star
    V.V. Lozin
    Discrete Mathematics 257 (2002) 83-100.
    Preprint 

  1. On maximum induced matchings in bipartite graphs
    V.V. Lozin
    Information Processing Letters 81 (1) (2002) 7-11.
    Preprint 

2001

  1. An attractive class of bipartite graphs
    R. Boliac and V.V. Lozin
    Discussiones Mathematicae Graph Theory 21 (2) (2001) 293-301.
    Preprint 

  1. A note on alpha-redundant vertices in graphs
    A. Brandstädt and V.V. Lozin
    Discrete Applied Mathematics 108 (2001) 301-308
    Abstract 

  1. On orthogonal representations of graphs
    V.E. Alekseev and V.V. Lozin
    Discrete Mathematics 226 (2001) 359-363
    Preprint 

2000

  1. On the jump number problem in hereditary classes of bipartite graphs
    M.U. Gerber and V.V. Lozin
    Order, 17 (4):377-385, 2000.
    Abstract

  1. Conic reduction of graphs for the stable set problem
    V.V. Lozin
    Discrete Mathematics 222 (2000) 199-211
    Abstract 

  1. Stability in P5- and banner-free graphs
    V.V. Lozin
    European Journal of Operational Research 125 (2000) 292-297
    Abstract 

  1. On a generalization of bi-complement reducible graphs
    V.V. Lozin
    Lecture Notes in Computer Science Vol. 1893 (2000) 528-537
    Abstract 

  1. E-free bipartite graphs
    V.V. Lozin
    Discrete Analysis and Operations Research Ser 1, Vol. 7 (2000) 49-66 (in Russian).
    Abstract 

1997

  1. On minimal universal graphs for hereditary classes
    V.V. Lozin
    Discrete Mathematics and Applications 7 (1997) 295-304
    translation from Diskretn. Mat. 9 No.2 (1997) 106-115 .
    Abstract 

1996

  1. Canonical partitions of graphs
    V.V. Lozin
    Discrete analysis and operations research. Mathematics and its Applications. 355 (1996) 163-172
    translation from Sibirsk. Zh. Issled. Oper Vol.1 No. 3 (1994) 49-59 .
    Abstract

1986

  1. Vertex coding of graphs in automatic decoding
    V.V. Lozin
    Combinatorial-algebraic methods in applied mathematics (1986) 73-83 ( in Russian).
    Abstract