Kristina Vušković
- Position
- Professor in Algorithms and Combinatorics
Publications
-
- Tree independence number I. (Even hole, diamond, pyramid)-free graphs
T. Abrishami, B. Alecu, M. Chudnovsky, S. Hajebi, S. Spirkl and K. Vušković,
to appear in Journal of Graph Theory
- Tree independence number I. (Even hole, diamond, pyramid)-free graphs
-
- Claw-free β-perfect graphs
J. Horsfield, K. Vušković,
submitted
- Claw-free β-perfect graphs
-
- Induced subgraphs and tree decompositions V. One neighbor in a hole
Tara Abrishmani, Bogdan Alecu, Maria Chudnovsky, Sepehr Hajebi, Sophie Spirkl and K. Vušković
to appear in the Journal of Graph Theory
- Induced subgraphs and tree decompositions V. One neighbor in a hole
-
- When all holes have the same length
J. Horsfield, M. Priessmann, C. Robin, N.L.D. Sintiari, N. Trotignon and K. Vušković,
(2022) arXiv:2203.11571v1
- When all holes have the same length
-
- Bisimplicial separators
M. Milanic, I. Penev, N. Pivac and K. Vušković,
to appear in Journal of Graph Theory
- Bisimplicial separators
-
- Graphs with all holes the same length
L. Cook, J. Horsfield, M. Preissmann, C. Robin, P. Seymour, N.L.D. Sintiari, N. Trotignon
and K. Vušković,
submitted to Journal of Combinatorial Theory B.
- Graphs with all holes the same length
-
- Submodular functions and perfect graphs
T. Abrishami, M. Chudnovsky, C. Dibekand K. Vušković
to appear in Mathematics of Operations Research.
- Submodular functions and perfect graphs
-
- Induced subgraphs and tree decompositions II. Towards walls and their line graphs in graphs of bounded degree
T. Abrishami, M. Chudnovsky, C. Dibek, S. Hajebi, P. Rzazewski, S. Spirkl and K. Vušković,
to appear in Journal of Combinatorial Theory B.
- Induced subgraphs and tree decompositions II. Towards walls and their line graphs in graphs of bounded degree
-
- Induced subgraphs and tree decompositions I. Even-hole-free graphs of bounded degree,
T. Abrishami, M. Chudnovsky and K. Vušković,
Journal of Combinatorial Theory B 157 (2022) 144-175.
- Induced subgraphs and tree decompositions I. Even-hole-free graphs of bounded degree,
-
- Graphs with polynomially many minimal separators
T. Abrishami, M. Chudnovsky, C. Dibek, S. Thomassé, N. Trotignon and K. Vušković
to appear in Journal of Combinatorial Theory B
- Graphs with polynomially many minimal separators
-
- Hadwiger’s Conjecture for some hereditary classes of graphs: a survey
K. Cameron and K. Vušković
Bulletin of the EATCS 131, The Algorithmics Column by T. Erlebach (2020).
- Hadwiger’s Conjecture for some hereditary classes of graphs: a survey
-
- Counting weighted independent sets beyond the permanent
M. Dyer, M. Jerum, H. Muller and K. Vušković
to appear in SIAM Journal on Discrete Mathematics
- Counting weighted independent sets beyond the permanent
-
- Two classes of β-perfect graphs that do not necessarily have simplicial extremes
J. Horsfield and K. Vušković
to appear in Discrete Mathematics
- Two classes of β-perfect graphs that do not necessarily have simplicial extremes
-
- Maximum independent sets in (pyramid, even hole)-free graphs
M. Chudnovsky, S. Thomassé, N. Trotignon and K. Vušković
arXiv:1912.11246 (2019)
- Maximum independent sets in (pyramid, even hole)-free graphs
-
- Coloring rings
F. Maffray, I. Penev and K. Vušković
Journal of Graph Theory 96 (4) (2021) 642-683
- Coloring rings
-
- The (theta, wheel)-free graphs, Part I: only-prism and only-pyramid graphs
E. Diot, M. Radovanović, N. Trotignon and K. Vušković
Journal of Combinatorial Theory B 143 (2020) 123-147.
- The (theta, wheel)-free graphs, Part I: only-prism and only-pyramid graphs
-
- The (theta, wheel)-free graphs, Part II: structure theorem
M. Radovanović, N. Trotignon and K. Vušković
Journal of Combinatorial Theory B 143 (2020) 148-184.
- The (theta, wheel)-free graphs, Part II: structure theorem
-
- The (theta, wheel)-free graphs, Part III: cliques, stable sets and coloring
M. Radovanović, N. Trotignon and K. Vušković
Journal of Combinatorial Theory B 143 (2020) 185-218. - The (theta, wheel)-free graphs, Part IV: induced paths and cycles
M. Radovanović, N. Trotignon and K. Vušković
to appear in Journal of Combinatorial Theory B.
- The (theta, wheel)-free graphs, Part III: cliques, stable sets and coloring
-
- Clique-cutsets beyond chordal graphs
V. Boncompagni, I. Penev and K. Vušković
Journal of Graph Theory 91 (2019) 192-246.
- Clique-cutsets beyond chordal graphs
-
- Triangle-free graphs that do not contain an induced subdivision of K4 are 3-colorable
M. Chudnovsky, C.-H. Liu, O. Schaudt, S. Spirkl, N. Trotignon and K. Vušković
Journal of Graph Theory 92 (2) pages 67-95, 2019
- Triangle-free graphs that do not contain an induced subdivision of K4 are 3-colorable
-
- On rank-width of (diamond, even hole)-free graphs
I. Adler, N.K. Le, H. Muller, M. Radovanović, N. Trotignon and K. Vušković
Discrete Mathematics and Theoretical Computer Science 19 (1), 2017.
- On rank-width of (diamond, even hole)-free graphs
-
- Structure and algorithms for (cap, even hole)-free graphs
K. Cameron, M.V.G. da Silva, S. Huang and K. Vušković
Discrete Mathematics 341 (2) pages 463-473, 2018.
- Structure and algorithms for (cap, even hole)-free graphs
-
- The structure of (theta, pyramid, 1-wheel, 3-wheel)-free graphs
V. Boncompagni, M. Radovanović and K. Vušković
Journal of Graph Theory 90 (4) (2019) 591-628.
- The structure of (theta, pyramid, 1-wheel, 3-wheel)-free graphs
-
- Coloring sqaure-free Berge graphs
M. Chudnovsky, I. Lo, F. Maffray, N. Trotignon and K. Vušković
Journal of Combinatorial Theory B 135 (2019) 96-128.
- Coloring sqaure-free Berge graphs
-
- On triangle-free graphs that do not contain a subdivision of the complete graph on four vertices as an induced subgraph
N. Trotignon and K. Vušković
Journal of Graph Theory 84, pages 233-248, 2017.
- On triangle-free graphs that do not contain a subdivision of the complete graph on four vertices as an induced subgraph
-
- A polynomial Turing-kernel for weighted independent set in bull-free graphs
S. Thomassé, N. Trotignon and K. Vušković
Algorithmica 77 pages 619-641, 2017.
- A polynomial Turing-kernel for weighted independent set in bull-free graphs
-
- A polynomial Turing-kernel for weighted independent set problem in bull-free graphs
S. Thomassé, N. Trotignon and K. Vušković
Graph-Theoretic Concepts in Computer Science, WG 2014, Lecture Notes in Computer Science, Springer-Verlag 8747 , pages 408-419, 2014.
- A polynomial Turing-kernel for weighted independent set problem in bull-free graphs
-
- Coloring perfect graphs with no balanced skew-partitions
M. Chudnovsky, N. Trotignon, T. Trunck and K. Vušković
Journal of Combinatorial Theory B 115 , pages 26-65, 2015.
- Coloring perfect graphs with no balanced skew-partitions
-
- Vertex elimination ordering for hereditary graph classes
P. Aboulker, P. Charbit, N. Trotignon, and K. Vušković
Discrete Mathematics 338 , pages 825-834, 2015.
- Vertex elimination ordering for hereditary graph classes
-
- Linear balanceable and subcubic balanceable graphs
P. Aboulker, M. Radovanović, N. Trotignon, T. Trunck and K. Vušković
Journal of Graph Theory 75 (2) , pages 150-166, 2014.
- Linear balanceable and subcubic balanceable graphs
-
- The world of hereditary graph classes viewed through Truemper configurations
K. Vušković
Chapter 7 in Surveys in Combinatorics, London Mathematical Society Lecture Note Series 409 , edited by S.R. Blackburn, S. Gerke and M. Wildon, Cambridge University Press, pages 265-325, 2013.
- The world of hereditary graph classes viewed through Truemper configurations
-
- Decomposition of even-hole-free graphs with star cutsets and 2-joins
M.V.G. da Silva and K. Vušković
Journal of Combinatorial Theory B 103 , pages 144-183, 2013.
- Decomposition of even-hole-free graphs with star cutsets and 2-joins
-
- A class of three-colorable triangle-free graphs
M. Radovanović and K. Vušković
Journal of Graph Theory 72 (4) , pages 430-439, 2013.
- A class of three-colorable triangle-free graphs
-
- Graphs that do not contain a cycle with a node that has at least two neighbors on it
P. Aboulker, M. Radovanović, N. Trotignon and K. Vušković
SIAM Journal on Discrete Mathematics 26(4), pages 1510-1531, 2012.
- Graphs that do not contain a cycle with a node that has at least two neighbors on it
-
- Combinatorial optimization with 2-joins
N. Trotignon and K. Vušković
Journal of Combinatorial Theory B 102 , pages 153-185, 2012.
- Combinatorial optimization with 2-joins
-
- Detecting 2-joins faster
P. Charbit, M. Habib, N. Trotignon and K. Vušković
Journal of Discrete Algorithms 17 , pages 60-66, 2012.
- Detecting 2-joins faster
-
- On Roussel and Rubio type lemmas and their consequences
N. Trotignon and K. Vušković
Discrete Mathematics 311 , pages 684-687, 2011.
- On Roussel and Rubio type lemmas and their consequences
-
- Even-hole-free graphs: a survey
K. Vušković
Applicable Analysis and Discrete Mathematics 4 (2) , pages 219-240, 2010.
- Even-hole-free graphs: a survey
-
- Chromatic index of graphs with no cycle with a unique chord
R.C.S. Machado, C.M.H. de Figueiredo and K. Vušković
Theoretical Computer Science 411 , pages 1221-1234, 2010.
- Chromatic index of graphs with no cycle with a unique chord
-
- A structure theorem for graphs with no cycle with a unique chord and its consequences
N. Trotignon and K. Vušković
Journal of Graph Theory 63 (1), pages 31-67, 2010.
- A structure theorem for graphs with no cycle with a unique chord and its consequences
-
- Even-hole-free graphs that do not contain diamonds: a structure theorem and its consequences
T. Kloks, H. Muller and K. Vušković
Journal of Combinatorial Theory B 99 , pages 733-800, 2009.
- Even-hole-free graphs that do not contain diamonds: a structure theorem and its consequences
-
- Algorithms for square-3PC(.,.)-free Berge graphs
F. Maffray, N. Trotignon and K. Vušković
SIAM Journal on Discrete Mathematics 22 (1), pages 51-71, 2008.
- Algorithms for square-3PC(.,.)-free Berge graphs
-
- Triangulated neighborhoods in even-hole-free graphs
M.V.G. da Silva and K. Vušković
Discrete Mathematics 307 , pages 1065-1073, 2007.
- Triangulated neighborhoods in even-hole-free graphs
-
- Balanced matrices
M. Conforti, G. Cornuéjols and K. Vušković
Discrete Mathematics 306 , pages 2411-2437, 2006.
- Balanced matrices
-
- Odd hole recognition in graphs of bounded clique size
M. Conforti, G. Cornuéjols, X. Liu, K. Vušković and G. Zambelli
SIAM Journal on Discrete Mathematics 20 , No. 1, pages 42-48, 2006.
- Odd hole recognition in graphs of bounded clique size
-
- Recognizing Berge graphs
M. Chudnovsky, G. Cornuéjols, X. Liu, P. Seymour and K. Vušković
Combinatorica 25 (2), pages 143-186, 2005.
- Recognizing Berge graphs
-
- A polynomial algorithm for recognizing perfect graphs
G. Cornuéjols, X. Liu and K. Vušković
Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science , Cambridge, Massacussets, USA, pages 20-27, 2003.
- A polynomial algorithm for recognizing perfect graphs
-
- Square-free perfect graphs
M. Conforti, G. Cornuéjols and K. Vušković
Journal of Combinatorial Theory B 90 (2), pages 257-307, 2004.
- Square-free perfect graphs
-
- Decomposing Berge graphs containing proper wheels
M. Conforti, G. Cornuéjols, K. Vušković and G. Zambelli
preprint (2002).
- Decomposing Berge graphs containing proper wheels
-
- Decomposition of odd-hole-free graphs by double star cutsets and 2-joins
M. Conforti, G. Cornuéjols and K. Vušković
Discrete Applied Mathematics 141 (1-3), pages 41-91, 2004,
Special issue dedicated to the Brazilian Symposium on Graphs, Algorithms and Combinatorics, Fortaleza, March 17-19, 2001 - Edited by B.A. Reed, S.W. Song and J.L.Szwarcfiter.
- Decomposition of odd-hole-free graphs by double star cutsets and 2-joins
-
- Even-hole-free graphs, Part I: Decomposition theorem
M. Conforti, G. Cornuéjols, A. Kapoor and K. Vušković
Journal of Graph Theory 39 , pages 6-49, 2002.
- Even-hole-free graphs, Part I: Decomposition theorem
-
- Even-hole-free graphs, Part II: Recognition algorithm
M. Conforti, G. Cornuéjols, A. Kapoor and K. Vušković
Journal of Graph Theory 40 , pages 238-266, 2002.
- Even-hole-free graphs, Part II: Recognition algorithm
-
- The graph sandwich problem for 1-join composition is NP-complete
C. M. H. de Figueiredo, S. Klein and K. Vušković
Discrete Applied Mathematics 121 (1-3), pages 73-82, 2002.
- The graph sandwich problem for 1-join composition is NP-complete
-
- Perfect graphs, partitionable graphs and cutsets
M. Conforti, G. Cornuéjols, G. Gasparyan and K. Vušković
Combinatorica 22 (1), pages 19-33, 2002.
- Perfect graphs, partitionable graphs and cutsets
-
- Recognition of quasi-Meyniel graphs
C. M. H. de Figueiredo and K. Vušković
Discrete Applied Mathematics 113 (2-3), pages 255-260, 2001.
- Recognition of quasi-Meyniel graphs
-
- Balanced 0,+1,-1 matrices, Part I: Decomposition
M. Conforti, G. Cornuéjols, A. Kapoor and K. Vušković
Journal of Combinatorial Theory B 81 (2), pages 243-274, 2001
- Balanced 0,+1,-1 matrices, Part I: Decomposition
-
- Balanced 0,+1,-1 matrices, Part II: Recognition algorithm
M. Conforti, G. Cornuéjols, A. Kapoor and K. Vušković
Journal of Combinatorial Theory B 81 (2), pages 275-306, 2001.
- Balanced 0,+1,-1 matrices, Part II: Recognition algorithm
-
- Triangle-free graphs that are signable without even holes
M. Conforti, G. Cornuéjols, A. Kapoor and K. Vušković
Journal of Graph Theory 34 , pages 204-220, 2000.
- Triangle-free graphs that are signable without even holes
-
- A class of β-perfect graphs
C. M. H. de Figueiredo and K. Vušković
Discrete Mathematics 216 , pages 169-193, 2000.
- A class of β-perfect graphs
-
- Balanced cycles and holes in bipartite graphs
M. Conforti, G. Cornuéjols and K. Vušković
Discrete Mathematics 199 (1-3), pages 27-33, 1999.
Discrete Mathematics, Editors' Choice 1999.
- Balanced cycles and holes in bipartite graphs
-
- Even and odd holes in cap-free graphs
M. Conforti, G. Cornuéjols, A. Kapoor and K. Vušković
Journal of Graph Theory 30 , pages 289-308, 1999.
- Even and odd holes in cap-free graphs
-
- Perfect, ideal and balanced matrices: A survey
M. Conforti, G. Cornuéjols, A. Kapoor and K. Vušković
Ricerca Operativa 26 (80), pages 65-80, 1997.
Invited Review, European Journal of Operational Research 133 , pages 455-461, 2001.
- Perfect, ideal and balanced matrices: A survey
-
- Universally signable graphs
M. Conforti, G. Cornuéjols, A. Kapoor and K. Vušković
Combinatorica 17 (1), pages 67-77, 1997.
- Universally signable graphs
-
- Finding an even hole in a graph
M. Conforti, G. Cornuéjols, A. Kapoor and K. Vušković
Proceedings of the $38^{th}$ Annual Conference on Foundations of Computer Science , pages 480-485, 1997.
- Finding an even hole in a graph
-
- Perfect, Ideal and Balanced Matrices
M. Conforti, G. Cornuéjols, A. Kapoor and K. Vušković
a chapter in Annotated Bibliographies in Combinatorial Optimization edited by M. Dell'Amico, F. Maffioli and S. Martelo; John Wiley and Sons, Ltd., pages 81-94, 1997.
- Perfect, Ideal and Balanced Matrices
-
- Perfect matchings in balanced hypergraphs
M. Conforti, G. Cornuéjols, A. Kapoor and K. Vušković
Combinatorica 16 (3), pages 325-329, 1996.
- Perfect matchings in balanced hypergraphs
-
- A Mickey-Mouse decomposition theorem
M. Conforti, G. Cornuéjols, A. Kapoor and K. Vušković
Proceedings of the Fourth International Integer Programming and Combinatorial Optimization Conference , Balas and Clausen eds., pages 321-328, Springer Verlag, 1995.
- A Mickey-Mouse decomposition theorem
-
- Balanced matrices: A survey
M. Conforti, G. Cornuéjols, A. Kapoor, M. R. Rao and K. Vušković
Mathematical Programming: State of the Art 1994 , J. R. Birge and K. G. Murty eds., pages 1-33, The University of Michigan Press, 1994. - Recognizing balanced 0,+1,-1 matrices
M. Conforti, G. Cornuéjols, A. Kapoor and K. Vušković
Proceedings of the Fifth Annual ACM-SIAM Symposium on Discrete Algorithms , pages 103-111, 1994.
- Balanced matrices: A survey