Clément Dallard

collaborators

9 papers

math.CO2026

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 $G$ and an integer $k$ , whether $G$ admits a colouring $c$ with sum $\sum_{v \in V} c (v) \leq k$ . We study the complexity of Chromatic S…

math.CO2025

Awesome graph parameters

Kenny BeÅ¡ter Å torgel, ClÃ©ment Dallard, Vadim Lozin +2

For a graph $G$ , we denote by $I^\pm (G)$ the size of a maximum independent set and by $I ¨ (G)$ the size of a maximum clique in $G$ . Our paper lies on the edge of two lines of research,…

cs.DS2025

Induced Minor Models. II. Sufficient conditions for polynomial-time detection of induced minors

ClÃ©ment Dallard, MaÃ«l Dumas, Claire Hilaire +1

The $H$ -Induced Minor Containment problem ( $H$ -IMC) consists in deciding if a fixed graph $H$ is an induced minor of a graph $G$ given as input, that is, whether $H$ can be obtaine…

math.CO2025

Induced Minor Models. I. Structural Properties and Algorithmic Consequences

Nicolas Bousquet, ClÃ©ment Dallard, MaÃ«l Dumas +4

A graph $H$ is said to be an induced minor of a graph $G$ if $H$ can be obtained from $G$ by a sequence of vertex deletions and edge contractions. Equivalently, $H$ is an induced m…

cs.DS2025

Computing Tree Decompositions with Small Independence Number

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…

cs.GT2025

Allocation of Indivisible Items with a Common Preference Graph: Minimizing Total Dissatisfaction

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…