12 citations · 49 across the 20 of their papers we have counts for
15 papers · 1 filter
Density of -critical signed graphs
Laurent Beaudou, Penny Haxell, Kathryn Nurse +2
We say that a signed graph is -critical if it is not -colorable but every one of its proper subgraphs is -colorable. Using the definition of colorability due to Naserasr,…
Homomorphism bounds of signed bipartite -minor-free graphs and edge-colorings of -regular -minor-free multigraphs
Laurent Beaudou, Florent Foucaud, Reza Naserasr
A signed graph is a graph and a subset of its edges which corresponds to an assignment of signs to the edges: edges in are negative while edges not in are…
Bounding the Number of Minimal Transversals in Tripartite 3-Uniform Hypergraphs
Alexandre Bazin, Laurent Beaudou, Giacomo Kahn +1
We bound the number of minimal hypergraph transversals that arise in tri-partite 3-uniform hypergraphs, a class commonly found in applications dealing with data. Let H be such a hy…
Broadcast domination and multipacking: bounds and the integrality gap
Laurent Beaudou, Richard C. Brewster, Florent Foucaud
The dual concepts of coverings and packings are well studied in graph theory. Coverings of graphs with balls of radius one and packings of vertices with pairwise distances at least…
A lower bound on the size of an absorbing set in an arc-coloured tournament
Laurent Beaudou, Luc Devroye, Gena Hahn
Bousquet, Lochet and Thomassé recently gave an elegant proof that for any integer , there is a least integer such that any tournament whose arcs are coloured with col…
Octal Games on Graphs: The game 0.33 on subdivided stars and bistars
Laurent Beaudou, Pierre Coupechoux, Antoine Dailly +4
Octal games are a well-defined family of two-player games played on heaps of counters, in which the players remove alternately a certain number of counters from a heap, sometimes b…
Homomorphism bounds and edge-colourings of -minor-free graphs
Laurent Beaudou, Florent Foucaud, Reza Naserasr
We present a necessary and sufficient condition for a graph of odd-girth to bound the class of -minor-free graphs of odd-girth (at least) , that is, to admit a ho…
Smallest -critical graphs of odd-girth
Laurent Beaudou, Florent Foucaud, Reza Naserasr
Given a graph , a graph is called -critical if does not admit a homomorphism to , but any proper subgraph of does. Observe that -critical graphs are t…
Bounding the order of a graph using its diameter and metric dimension: a study through tree decompositions and VC dimension
Laurent Beaudou, Florent Foucaud, Peter Dankelmann +3
The metric dimension of a graph is the minimum size of a set of vertices such that each vertex is uniquely determined by the distances to the vertices of that set. Our aim is to up…
Homomorphisms of binary Cayley graphs
Laurent Beaudou, Reza Naserasr, Claude Tardif
A binary Cayley graph is a Cayley graph based on a binary group. In 1982, Payan proved that any non-bipartite binary Cayley graph must contain a generalized Mycielski graph of an o…
On a class of intersection graphs
Mourad Baïou, Laurent Beaudou, Zhentao Li +1
Given a directed graph D = (V,A) we define its intersection graph I(D) = (A,E) to be the graph having A as a node-set and two nodes of I(D) are adjacent if their corresponding arcs…
A De Bruijn-Erdos theorem for chordal graphs
Laurent Beaudou, Adrian Bondy, Xiaomin Chen +5
A special case of a combinatorial theorem of De Bruijn and Erdos asserts that every noncollinear set of n points in the plane determines at least n distinct lines. Chen and Chvatal…
Making a graph crossing-critical by multiplying its edges
Laurent Beaudou, César Hernández-Vélez, Gelasio Salazar
A graph is crossing-critical if the removal of any of its edges decreases its crossing number. This work is motivated by the following question: to what extent is crossing- critica…
Lines in hypergraphs
Laurent Beaudou, Adrian Bondy, Xiaomin Chen +5
One of the De Bruijn - Erdos theorems deals with finite hypergraphs where every two vertices belong to precisely one hyperedge. It asserts that, except in the perverse case where a…
Drawing disconnected graphs on the Klein bottle
Laurent Beaudou, Antoine Gerbaud, Roland Grappe +1
We prove that two disjoint graphs must always be drawn separately on the Klein bottle, in order to minimize the crossing number of the whole drawing.