Source author record

Rémi Pellerin

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Computational Complexity Data Structures and Algorithms Discrete Mathematics math.CO

Catalog footprint

Research overview

2works

4topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2023arXiv

Solution to a problem of Katona on counting cliques of weighted graphs

A subset $I$ of the vertex set $V(G)$ of a graph $G$ is called a $k$ -clique independent set of $G$ if no $k$ vertices in $I$ form a $k$ -clique of $G$ . An independent set is a $2$ -clique independent set. Let $π_k(G)$ denote the number of $k$ -cliques of $G$ . For a function $w: V(G) \rightarrow \{0, 1, 2, \dots\}$ , let $G(w)$ be the graph obtained from $G$ by replacing each vertex $v$ by a $w(v)$ -clique $K^v$ and making each vertex of $K^u$ adjacent to each vertex of $K^v$ for each edge $\{u,v\}$ of $G$ . For an integer $m \geq 1$ , consider any $w$ with $\sum_{v \in V(G)} w(v) = m$ . For $U \subseteq V(G)$ , we say that $w$ is uniform on $U$ if $w(v) = 0$ for each $v \in V(G) \setminus U$ and, for each $u \in U$ , $w(u) = \left\lfloor m/|U| \right\rfloor$ or $w(u) = \left\lceil m/|U| \right\rceil$ . Katona asked if $π_k(G(w))$ is smallest when $w$ is uniform on a largest $k$ -clique independent set of $G$ . He placed particular emphasis on the Sperner graph $B_n$ , given by $V(B_n) = \{X \colon X \subseteq \{1, \dots, n\}\}$ and $E(B_n) = \{\{X,Y\} \colon X \subsetneq Y \in V(B_n)\}$ . He provided an affirmative answer for $k = 2$ (and any $G$ ). We determine graphs for which the answer is negative for every $k \geq 3$ . These include $B_n$ for $n \geq 2$ . Generalizing Sperner's Theorem and a recent result of Qian, Engel and Xu, we show that $π_k(B_n(w))$ is smallest when $w$ is uniform on a largest independent set of $B_n$ . We also show that the same holds for complete multipartite graphs and chordal graphs. We show that this is not true of every graph, using a deep result of Bohman on triangle-free graphs.

preprint2022arXiv

A quasi-quadratic vertex Kernel for Cograph edge editing

We provide a $O(k^2 \mathrm{log} k)$ vertex kernel for cograph edge editing. This improves a cubic kernel found by Guillemot, Havet, Paul and Perez [1] which involved four reduction rules. We generalize one of their rules, based on packing of induced paths of length four, by introducing t-modules, which are modules up to t edge modifications. The key fact is that large t-modules cannot be edited more than t times, and this allows to obtain a near quadratic kernel. The extra $\mathrm{log} k$ factor seems tricky to remove as it is necessary in the combinatorial lemma on trees which is central in our proof. Nevertheless, we think that a quadratic bound should be reachable.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.