11 citations · 18 across the 16 of their papers we have counts for
18 papers
Determining the Complexity of Chromatic Sum in Classes Defined by a Set of Forbidden Graphs
Clément Dallard, Daniël Paulusma, Erik Jan van Leeuwen
The Chromatic Sum problem asks, given a graph and an integer , whether admits a colouring with sum . We study the complexity of Chromatic S…
Awesome graph parameters
Kenny Bešter Štorgel, Clément Dallard, Vadim Lozin +2
For a graph , we denote by the size of a maximum independent set and by the size of a maximum clique in . Our paper lies on the edge of two lines of research, r…
Layered tree-independence number and clique-based separators
Clément Dallard, Martin Milanič, Andrea Munaro +1
Motivated by a question of Galby, Munaro, and Yang (SoCG 2023) asking whether every graph class of bounded layered tree-independence number admits clique-based separators of sublin…
On constrained intersection representations of graphs and digraphs
Ferdinando Cicalese, Clément Dallard, Martin Milanič
We study the problem of determining optimal directed intersection representations of DAGs in a model introduced by Kostochka, Liu, Machado, and Milenkovic [ISIT2019]: vertices are…
Induced Minor Models. II. Sufficient conditions for polynomial-time detection of induced minors
Clément Dallard, Maël Dumas, Claire Hilaire +1
The -Induced Minor Containment problem (-IMC) consists in deciding if a fixed graph is an induced minor of a graph given as input, that is, whether can be obtaine…
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…
Induced Minor Models. I. Structural Properties and Algorithmic Consequences
Nicolas Bousquet, Clément Dallard, Maël Dumas +4
A graph is said to be an induced minor of a graph if can be obtained from by a sequence of vertex deletions and edge contractions. Equivalently, is an induced m…
Allocation of Indivisible Items with a Common Preference Graph: Minimizing Total Dissatisfaction
Nina Chiarelli, Clément Dallard, Andreas Darmann +4
Allocating indivisible items among a set of agents is a frequently studied discrete optimization problem. In the setting considered in this work, the agents' preferences over the i…
Minimizing Maximum Dissatisfaction in the Allocation of Indivisible Items under a Common Preference Graph
Nina Chiarelli, Clément Dallard, Andreas Darmann +4
We consider the task of allocating indivisible items to agents, when the agents' preferences over the items are identical. The preferences are captured by means of a directed acycl…
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…
On minimally tough chordal graphs
Clément Dallard, Blas Fernández, Gyula Y. Katona +2
Katona and Varga showed that for any rational number , no chordal graph is minimally -tough, while Katona and Khan characterized all minimally -tough, chordal…
Computing Tree Decompositions with Small Independence Number
Clément Dallard, Fedor V. Fomin, Petr A. Golovach +2
The independence number of a tree decomposition is the maximum of the independence numbers of the subgraphs induced by its bags. The tree-independence number of a graph is the mini…
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,…
Finding -community structures in special graph classes
Narmina Baghirova, Clément Dallard, Bernard Ries +1
For a fixed integer , a -community structure in an undirected graph is a partition of its vertex set into sets called communities, each of size at least two, such th…
Allocation of Indivisible Items with Individual Preference Graphs
Nina Chiarelli, Clément Dallard, Andreas Darmann +5
This paper studies the allocation of indivisible items to agents, when each agent's preferences are expressed by means of a directed acyclic graph. The vertices of each preference…
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…
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…