BZPEERReading, trust and collaboration for research
Menu

Discover

GraphFollow connections around a paper, topic or saved view.

Workspaces

HomePick up where your research flow left off.InboxHandle requests, replies and notifications from one place.CollectionsCurate reading lists, evidence sets and shareable dossiers.ResearchSee your private provenance graph, trail and imports.CollaborationMove from discovery into focused discussion rooms.PublishDraft, preview and publish full-text research articles.

Network

ExpertsFind specialists worth following or asking for help.CommunitiesJoin research circles organized around shared work.PartnersSee external organizations active around the same topics.

Opportunities

ListingsBrowse roles, calls and collaborations with clearer fit signals.

Account

Log inReturn to your reading and collaboration workspace.Create accountStart saving work, following people and joining teams.
Log inCreate account

Researcher profile

Pierre Aboulker

Pierre Aboulker contributes to research discovery and scholarly infrastructure.

ResearcherAffiliation not importedOpen to collaborate
math.CODiscrete MathematicsComputational ComplexityData Structures and Algorithms

Trust snapshot

Quick read

Trust 21 - EmergingVerification L1Unclaimed author
7works
0followers
4topics
4close collaborators

Actions

Decide how to stay connected

Follow researcher0

Identity and collaboration

How to connect with this researcher

Claiming links this public author record to a researcher profile and unlocks direct collaboration workflows.

Log in to claim

Direct collaboration

Open a focused conversation when the fit is right

Claim this author entity first to unlock direct invitations.

Research graph

See the researcher in context

Open full explorer

Inspect adjacent work, topics, institutions and collaborators without jumping out to a separate graph page.

Building this graph slice

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

Published work

7 published item(s)

preprint2023arXiv

(P6, triangle)-free digraphs have bounded dichromatic number

The dichromatic number of an oriented graph is the minimum size of a partition of its vertices into acyclic induced subdigraphs. We prove that oriented graphs with no induced directed path on six vertices and no triangle have bounded dichromatic number. This is one (small) step towards the general conjecture asserting that for every oriented tree T and every integer k, any oriented graph that does not contain an induced copy of T nor a clique of size k has dichromatic number at most some function of k and T.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

On the minimum number of arcs in $k$-dicritical oriented graphs

The dichromatic number $\dic(D)$ of a digraph $D$ is the least integer $k$ such that $D$ can be partitioned into $k$ directed acyclic digraphs. A digraph is $k$-dicritical if $\dic(D) = k$ and each proper subgraph $D&#39;$ of $D$ satisfies $\dic(D&#39;) \leq k-1$. An oriented graph is a digraph with no directed cycle of length $2$. For integers $k$ and $n$, we denote by $o_k(n)$ the minimum number of edges of a $k$-critical oriented graph on $n$ vertices (with the convention $o_k(n)=+\infty$ if there is no $k$-dicritical oriented graph of order $n$). The main result of this paper is a proof that $o_3(n) \geq \frac{7n+2}{3}$ together with a construction witnessing that $o_3(n) \leq \left \lceil \frac{5n}{2} \right \rceil$ for all $n \geq 12$. We also give a construction showing that for all sufficiently large $n$ and all $k\geq 3$, $o_k(n) < (2k-3)n$, disproving a conjecture of Hoshino and Kawarabayashi. Finally, we prove that, for all $k\geq 2$, $o_k(n) \geq \pth{ k - \frac{3}{4}-\frac{1}{4k-6}} n + \frac{3}{4(2k-3)}$, improving the previous best known lower bound of Bang-Jensen, Bellitto, Schweser and Stiebitz.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Vizing&#39;s and Shannon&#39;s Theorems for defective edge colouring

We call a multigraph $(k,d)$-edge colourable if its edge set can be partitioned into $k$ subgraphs of maximum degree at most $d$ and denote as $χ&#39;_{d}(G)$ the minimum $k$ such that $G$ is $(k,d)$-edge colourable. We prove that for every integer $d$, every multigraph $G$ with maximum degree $Δ$ is $(\lceil \fracΔ{d} \rceil, d)$-edge colourable if $d$ is even and $(\lceil \frac{3Δ- 1}{3d - 1} \rceil, d)$-edge colourable if $d$ is odd and these bounds are tight. We also prove that for every simple graph $G$, $χ&#39;_{d}(G) \in \{ \lceil \fracΔ{d} \rceil, \lceil \frac{Δ+1}{d} \rceil \}$ and characterize the values of $d$ and $Δ$ for which it is NP-complete to compute $χ&#39;_d(G)$. These results generalize several classic results on the chromatic index of a graph by Shannon, Vizing, Holyer, Leven and Galil.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Graphs with no induced house nor induced hole have the de Bruijn-Erdős property

A set of n points in the plane which are not all collinear defines at least n distinct lines. Chen and Chvátal conjectured in 2008 that a similar result can be achieved in the broader context of finite metric spaces. This conjecture remains open even for graph metrics. In this article we prove that graphs with no induced house nor induced cycle of length at least~5 verify the desired property. We focus on lines generated by vertices at distance at most 2, define a new notion of ``good pairs&#39;&#39; that might have application in larger families, and finally use a discharging technique to count lines in irreducible graphs.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Grundy Coloring & friends, Half-Graphs, Bicliques

The first-fit coloring is a heuristic that assigns to each vertex, arriving in a specified order $σ$, the smallest available color. The problem Grundy Coloring asks how many colors are needed for the most adversarial vertex ordering $σ$, i.e., the maximum number of colors that the first-fit coloring requires over all possible vertex orderings. Since its inception by Grundy in 1939, Grundy Coloring has been examined for its structural and algorithmic aspects. A brute-force $f(k)n^{2^{k-1}}$-time algorithm for Grundy Coloring on general graphs is not difficult to obtain, where $k$ is the number of colors required by the most adversarial vertex ordering. It was asked several times whether the dependency on $k$ in the exponent of $n$ can be avoided or reduced, and its answer seemed elusive until now. We prove that Grundy Coloring is W[1]-hard and the brute-force algorithm is essentially optimal under the Exponential Time Hypothesis, thus settling this question by the negative. The key ingredient in our W[1]-hardness proof is to use so-called half-graphs as a building block to transmit a color from one vertex to another. Leveraging the half-graphs, we also prove that b-Chromatic Core is W[1]-hard, whose parameterized complexity was posed as an open question by Panolan et al. [JCSS &#39;17]. A natural follow-up question is, how the parameterized complexity changes in the absence of (large) half-graphs. We establish fixed-parameter tractability on $K_{t,t}$-free graphs for b-Chromatic Core and Partial Grundy Coloring, making a step toward answering this question. The key combinatorial lemma underlying the tractability result might be of independent interest.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Colouring graphs with constraints on connectivity

A graph $G$ has maximal local edge-connectivity $k$ if the maximum number of edge-disjoint paths between every pair of distinct vertices $x$ and $y$ is at most $k$. We prove Brooks-type theorems for $k$-connected graphs with maximal local edge-connectivity $k$, and for any graph with maximal local edge-connectivity 3. We also consider several related graph classes defined by constraints on connectivity. In particular, we show that there is a polynomial-time algorithm that, given a 3-connected graph $G$ with maximal local connectivity 3, outputs an optimal colouring for $G$. On the other hand, we prove, for $k \ge 3$, that $k$-colourability is NP-complete when restricted to minimally $k$-connected graphs, and 3-colourability is NP-complete when restricted to $(k-1)$-connected graphs with maximal local connectivity $k$. Finally, we consider a parameterization of $k$-colourability based on the number of vertices of degree at least $k+1$, and prove that, even when $k$ is part of the input, the corresponding parameterized problem is FPT.

0 citations0 reviewsNo code linkedOpen access