66 citations · 323 across the 55 of their papers we have counts for
43 papers · 1 filter
There are no nontrivial chordal square-complementary graphs
Pierre Aboulker, Martin Milanič, Peter Muršič +1
We study square-complementary graphs (satisfying ). We show that in such graphs, no two vertices have comparable closed neighborhoods. This implies that…
A tame vs. feral dichotomy for graph classes excluding an induced minor or induced topological minor
Martin Milanič, Nevena Pivač
A minimal separator in a graph is an inclusion-minimal set of vertices that separates some fixed pair of nonadjacent vertices. A graph class is said to be tame if there exists a po…
On balanceable and simply balanceable regular graphs
Milad Ahanjideh, Martin Milanič, Mary Servatius
We continue the study of balanceable graphs, defined by Caro, Hansberg, and Montejano in 2021 as graphs such that any -coloring of the edges of a sufficiently large complete…
Treewidth versus clique number. IV. Tree-independence number of graphs excluding an induced star
Clément Dallard, Matjaž Krnc, O-joung Kwon +4
Many recent works address the question of characterizing induced obstructions to bounded treewidth. In 2022, Lozin and Razgon completely answered this question for graph classes de…
Bisimplicial separators
Martin Milanič, Irena Penev, Nevena Pivač +1
A minimal separator of a graph is a set such that there exist vertices with the property that separates from in , b…
Functionality of box intersection graphs
Clément Dallard, Vadim Lozin, Martin Milanič +2
Functionality is a graph complexity measure that extends a variety of parameters, such as vertex degree, degeneracy, clique-width, or twin-width. In the present paper, we show that…
Computing Well-Covered Vector Spaces of Graphs using Modular Decomposition
Martin Milanič, Nevena Pivač
A graph is well-covered if all its maximal independent sets have the same cardinality. This well studied concept was introduced by Plummer in 1970 and naturally generalizes to the…
Avoidability beyond paths
Vladimir Gurvich, Matjaž Krnc, Martin Milanič +1
The concept of avoidable paths in graphs was introduced by Beisegel, Chudnovsky, Gurvich, Milanič, and Servatius in 2019 as a common generalization of avoidable vertices and simpli…
Treewidth versus clique number. III. Tree-independence number of graphs with a forbidden structure
Clément Dallard, Martin Milanič, Kenny Štorgel
We continue the study of -bounded graph classes, that is, hereditary graph classes in which the treewidth can only be large due to the presence of a large clique,…
Treewidth versus clique number. II. Tree-independence number
Clément Dallard, Martin Milanič, Kenny Štorgel
In 2020, we initiated a systematic study of graph classes in which the treewidth can only be large due to the presence of a large clique, which we call -bounded. W…
Graphs with at most two moplexes
Clément Dallard, Robert Ganian, Meike Hatzel +2
A moplex is a natural graph structure that arises when lifting Dirac's classical theorem from chordal graphs to general graphs. While every non-complete graph has at least two mopl…
Complexity and algorithms for constant diameter augmentation problems
Eun Jung Kim, Martin Milanic, Jérôme Monnot +1
We study the following problem: for given integers and graph , can we obtain a graph with diameter via at most edge deletions ? We determine the computational comp…
On the degree sequences of dual graphs on surfaces
Endre Boros, Vladimir Gurvich, Martin Milanič +1
Given two graphs and with a one-to-one correspondence between their edges, when do and form a pair of dual graphs realizing the vertices and countries of a map…
Shifting paths to avoidable ones
Vladimir Gurvich, Matjaž Krnc, Martin Milanič +1
An extension of an induced path in a graph is an induced path such that deleting the endpoints of results in . An induced path in a graph is said to be avoidab…
Strong cliques in diamond-free graphs
Nina Chiarelli, Berenice Martínez Barona, Martin Milanič +2
A strong clique in a graph is a clique intersecting all inclusion-maximal stable sets. Strong cliques play an important role in the study of perfect graphs. We study strong cliques…
Treewidth versus clique number. I. Graph classes with a forbidden structure
Clément Dallard, Martin Milanič, Kenny Štorgel
Treewidth is an important graph invariant, relevant for both structural and algorithmic reasons. A necessary condition for a graph class to have bounded treewidth is the absence of…
Avoidable Vertices and Edges in Graphs
Jesse Beisegel, Maria Chudnovsky, Vladimir Gurvich +2
A vertex in a graph is simplicial if its neighborhood forms a clique. We consider three generalizations of the concept of simplicial vertices: avoidable vertices (also known as \te…
Minimal separators in graph classes defined by small forbidden induced subgraphs
Martin Milanič, Nevena Pivač
Minimal separators in graphs are an important concept in algorithmic graph theory. In particular, many problems that are NP-hard for general graphs are known to become polynomial-t…
Mind the Independence Gap
Tınaz Ekim, Didem Gözüpek, Ademir Hujdurović +1
The independence gap of a graph was introduced by Ekim et al. (2018) as a measure of how far a graph is from being well-covered. It is defined as the difference between the maximum…
A characterization of claw-free CIS graphs and new results on the order of CIS graphs
Liliana Alcón, Marisa Gutierrez, Martin Milanič
A graph is CIS if every maximal clique interesects every maximal stable set. Currently, no good characterization or recognition algorithm for the CIS graphs is known. We characteri…
Detecting strong cliques
Ademir Hujdurović, Martin Milanič, Bernard Ries
A strong clique in a graph is a clique intersecting every maximal independent set. We study the computational complexity of six algorithmic decision problems related to strong cliq…
Searching for square-complementary graphs: non-existence results and complexity of recognition
Ratko Darda, Martin Milanič, Miguel Pizaña
A graph is square-complementary (squco, for short) if its square and complement are isomorphic. We prove that there are no squco graphs with girth 6, that every bipartite graph is…
Characterizing and decomposing classes of threshold, split, and bipartite graphs via 1-Sperner hypergraphs
Endre Boros, Vladimir Gurvich, Martin Milanič
A hypergraph is said to be -Sperner if for every two hyperedges the smallest of their two set differences is of size one. We present several applications of -Sperner hypergra…
On two extensions of equimatchable graphs
Zakir Deniz, Tınaz Ekim, Tatiana Romina Hartinger +2
A graph is said to be equimatchable if all its maximal matchings are of the same size. In this work we introduce two extensions of the property of equimatchability by defining two…