BZPEER
More

Discover

About BZPEERSearchGraph

Research tools

HomeCollectionsResearchCollaborationPublish

Network

ExpertsCommunities

Opportunities

Listings

Account

Log inCreate account
Log inCreate account

Source author record

Pierre Aboulker

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

ResearcherUnclaimed source record
math.CODiscrete MathematicsComputational Complexitymath.MGData Structures and Algorithms

Catalog footprint

Research overview

18works
5topics
4close collaborators

Actions

Is this your work?

Log in to claim
Open graphBrowse papers

Published work

18 publications

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.

Open access
preprint2022arXiv

On the minimum number of arcs in kk-dicritical oriented graphs

The dichromatic number $\dic(D)$ of a digraph DD is the least integer kk such that DD can be partitioned into kk directed acyclic digraphs. A digraph is kk-dicritical if $\dic(D) = k$ and each proper subgraph D′D' of DD satisfies $\dic(D') \leq k-1$. An oriented graph is a digraph with no directed cycle of length 22. For integers kk and nn, we denote by ok(n)o_k(n) the minimum number of edges of a kk-critical oriented graph on nn vertices (with the convention ok(n)=+∞o_k(n)=+\infty if there is no kk-dicritical oriented graph of order nn). The main result of this paper is a proof that o3(n)≥7n+23o_3(n) \geq \frac{7n+2}{3} together with a construction witnessing that o3(n)≤⌈5n2⌉o_3(n) \leq \left \lceil \frac{5n}{2} \right \rceil for all n≥12n \geq 12. We also give a construction showing that for all sufficiently large nn and all k≥3k\geq 3, ok(n)<(2k−3)no_k(n) < (2k-3)n, disproving a conjecture of Hoshino and Kawarabayashi. Finally, we prove that, for all k≥2k\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.

Open access
preprint2022arXiv

Vizing's and Shannon's Theorems for defective edge colouring

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

Open 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'' that might have application in larger families, and finally use a discharging technique to count lines in irreducible graphs.

Open 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)n2k−1f(k)n^{2^{k-1}}-time algorithm for Grundy Coloring on general graphs is not difficult to obtain, where kk is the number of colors required by the most adversarial vertex ordering. It was asked several times whether the dependency on kk in the exponent of nn 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 '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 Kt,tK_{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.

Open access
preprint2016arXiv

χχ-bounded families of oriented graphs

A famous conjecture of Gyárfás and Sumner states for any tree TT and integer kk, if the chromatic number of a graph is large enough, either the graph contains a clique of size kk or it contains TT as an induced subgraph. We discuss some results and open problems about extensions of this conjecture to oriented graphs. We conjecture that for every oriented star SS and integer kk, if the chromatic number of a digraph is large enough, either the digraph contains a clique of size kk or it contains SS as an induced subgraph. As an evidence, we prove that for any oriented star SS, every oriented graph with sufficiently large chromatic number contains either a transitive tournament of order 33 or SS as an induced subdigraph. We then study for which sets P{\cal P} of orientations of P4P_4 (the path on four vertices) similar statements hold. We establish some positive and negative results.

Open access
preprint2016arXiv

Colouring graphs with constraints on connectivity

A graph GG has maximal local edge-connectivity kk if the maximum number of edge-disjoint paths between every pair of distinct vertices xx and yy is at most kk. We prove Brooks-type theorems for kk-connected graphs with maximal local edge-connectivity kk, 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 GG with maximal local connectivity 3, outputs an optimal colouring for GG. On the other hand, we prove, for k≥3k \ge 3, that kk-colourability is NP-complete when restricted to minimally kk-connected graphs, and 3-colourability is NP-complete when restricted to (k−1)(k-1)-connected graphs with maximal local connectivity kk. Finally, we consider a parameterization of kk-colourability based on the number of vertices of degree at least k+1k+1, and prove that, even when kk is part of the input, the corresponding parameterized problem is FPT.

Open access
preprint2015arXiv

De Bruijn-Erdős type theorems for graphs and posets

A classical theorem of De Bruijn and Erdős asserts that any noncollinear set of n points in the plane determines at least n distinct lines. We prove that an analogue of this theorem holds for graphs. Restricting our attention to comparability graphs, we obtain a version of the De Bruijn-Erdős theorem for partially ordered sets (posets). Moreover, in this case, we have an improved bound on the number of lines depending on the height of the poset. The extremal configurations are also determined.

Open access
preprint2014arXiv

Lines, betweenness and metric spaces

A classic theorem of Euclidean geometry asserts that any noncollinear set of nn points in the plane determines at least nn distinct lines. Chen and Chvátal conjectured that this holds for an arbitrary finite metric space, with a certain natural definition of lines in a metric space. We prove that in any metric space with nn points, either there is a line containing all the points or there are at least Ω(n)Ω(\sqrt{n}) lines. This is the first polynomial lower bound on the number of lines in general finite metric spaces. In the more general setting of pseudometric betweenness, we prove a corresponding bound of Ω(n2/5)Ω(n^{2/5}) lines. When the metric space is induced by a connected graph, we prove that either there is a line containing all the points or there are Ω(n4/7)Ω(n^{4/7}) lines, improving the previous Ω(n2/7)Ω(n^{2/7}) bound. We also prove that the number of lines in an nn-point metric space is at least n/5wn / 5w, where ww is the number of different distances in the space, and we give an Ω(n4/3)Ω(n^{4/3}) lower bound on the number of lines in metric spaces induced by graphs with constant diameter, as well as spaces where all the positive distances are from \{1, 2, 3\}.

Open access
preprint2014arXiv

The Chen-Chvátal conjecture for metric spaces induced by distance-hereditary graphs

A special case of a theorem of De Bruijn and Erdős asserts that any noncollinear set of nn points in the plane determines at least nn distinct lines. Chen and Chvátal conjectured a generalization of this result to arbitrary finite metric spaces, with a particular definition of lines in a metric space. We prove it for metric spaces induced by connected distance-hereditary graphs -- a graph GG is called distance-hereditary if the distance between two vertices uu and vv in any connected induced subgraph HH of GG is equal to the distance between uu and vv in GG.

Open access
preprint2013arXiv

Graphs that do not contain a cycle with a node that has at least two neighbors on it

We recall several known results about minimally 2-connected graphs, and show that they all follow from a decomposition theorem. Starting from an analogy with critically 2-connected graphs, we give structural characterizations of the classes of graphs that do not contain as a subgraph and as an induced subgraph, a cycle with a node that has at least two neighbors on the cycle. From these characterizations we get polynomial time recognition algorithms for these classes, as well as polynomial time algorithms for vertex-coloring and edge-coloring.

Open access
preprint2013arXiv

Linear balanceable and subcubic balanceable graphs

In [{Structural properties and decomposition of linear balanced matrices}, {\it Mathematical Programming}, 55:129--168, 1992], Conforti and Rao conjectured that every balanced bipartite graph contains an edge that is not the unique chord of a cycle. We prove this conjecture for balanced bipartite graphs that do not contain a cycle of length 4 (also known as linear balanced bipartite graphs), and for balanced bipartite graphs whose maximum degree is at most 3. We in fact obtain results for more general classes, namely linear balanceable and subcubic balanceable graphs. Additionally, we prove that cubic balanced graphs contain a pair of twins, a result that was conjectured by Morris, Spiga and Webb in [Balanced Cayley graphs and balanced planar graphs, {\it Discrete Mathematics}, 310:3228--3235, 2010].

Open access
preprint2013arXiv

Vertex elimination orderings for hereditary graph classes

We provide a general method to prove the existence and compute efficiently elimination orderings in graphs. Our method relies on several tools that were known before, but that were not put together so far: the algorithm LexBFS due to Rose, Tarjan and Lueker, one of its properties discovered by Berry and Bordat, and a local decomposition property of graphs discovered by Maffray, Trotignon and Vu\vsković. We use this method to prove the existence of elimination orderings in several classes of graphs, and to compute them in linear time. Some of the classes have already been studied, namely even-hole-free graphs, square-theta-free Berge graphs, universally signable graphs and wheel-free graphs. Some other classes are new. It turns out that all the classes that we study in this paper can be defined by excluding some of the so-called Truemper configurations. For several classes of graphs, we obtain directly bounds on the chromatic number, or fast algorithms for the maximum clique problem or the coloring problem.

Open access

Research graph

See the researcher in context

Open full explorer

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.