43 citations · 161 across the 15 of their papers we have counts for
17 papers
Feedback vertex sets of planar digraphs with fixed digirth
Simon Dreyer, Alexandre Pinlou, Petru Valicov
Let denote the size of a minimum feedback vertex set of a digraph . We study , which is the maximum over all -vertex planar digraphs of digirt…
Largest planar graphs of diameter and fixed maximum degree -- connection with fractional matchings
Antoine Dailly, Sasha Darmon, Ugo Giocanti +2
The degree diameter problem asks for the maximum possible number of vertices in a graph of maximum degree and diameter . In this paper, we focus on planar graphs of diameter…
Partitions of planar (oriented) graphs into a connected acyclic and an independent set
Stijn Cambie, François Dross, Kolja Knauer +2
A question at the intersection of Barnette's Hamiltonicity and Neumann-Lara's dicoloring conjecture is: Can every Eulerian oriented planar graph be vertex-partitioned into two acyc…
Computer assisted discharging procedure on planar graphs: application to 2-distance coloring
Hoang La, Petru Valicov
Using computational techniques we provide a framework for proving results on subclasses of planar graphs via discharging method. The aim of this paper is to apply these techniques…
Feedback vertex sets in (directed) graphs of bounded degeneracy or treewidth
Kolja Knauer, Hoang La, Petru Valicov
We study the minimum size of a feedback vertex set in directed and undirected -vertex graphs of given degeneracy or treewidth. In the undirected setting the bound $\frac{k-1…
Exact square coloring of subcubic planar graphs
Florent Foucaud, Hervé Hocquard, Suchismita Mishra +4
We study the exact square chromatic number of subcubic planar graphs. An exact square coloring of a graph G is a vertex-coloring in which any two vertices at distance exactly 2 rec…
Enumerating -arc-connected orientations
Sarah Blind, Kolja Knauer, Petru Valicov
We study the problem of enumerating the -arc-connected orientations of a graph , i.e., generating each exactly once. A first algorithm using submodular flow optimization is e…
(2, 3)-bipartite graphs are strongly 6-edge-choosable
Petru Valicov
Kang and Park recently showed that every cubic (loopless) multigraph is incidence 6-choosable [On incidence choosability of cubic graphs. \emph{arXiv}, April 2018]. Equivalently, e…
Cuts in matchings of 3-connected cubic graphs
Kolja Knauer, Petru Valicov
We discuss conjectures on Hamiltonicity in cubic graphs (Tait, Barnette, Tutte), on the dichromatic number of planar oriented graphs (Neumann-Lara), and on even graphs in digraphs…
Identification, location-domination and metric dimension on interval and permutation graphs. I. Bounds
Florent Foucaud, George B. Mertzios, Reza Naserasr +2
We consider the problems of finding optimal identifying codes, (open) locating-dominating sets and resolving sets of an interval or a permutation graph. In these problems, one asks…
On powers of interval graphs and their orders
Florent Foucaud, Reza Naserasr, Aline Parreau +1
It was proved by Raychaudhuri in 1987 that if a graph power is an interval graph, then so is the next power . This result was extended to -trapezoid graphs by Flo…
Planar digraphs without large acyclic sets
Kolja Knauer, Petru Valicov, Paul S. Wenger
Given a directed graph, an acyclic set is a set of vertices inducing a subgraph with no directed cycle. In this note we show that there exist oriented planar graphs of order fo…
Strong edge-coloring of -bipartite graphs
Julien Bensmail, Aurélie Lagoutte, Petru Valicov
A strong edge-coloring of a graph is an assignment of colors to edges such that every color class induces a matching. We here focus on bipartite graphs whose one part is of max…
Identification, location-domination and metric dimension on interval and permutation graphs. II. Algorithms and complexity
Florent Foucaud, George B. Mertzios, Reza Naserasr +2
We consider the problems of finding optimal identifying codes, (open) locating-dominating sets and resolving sets (denoted IDENTIFYING CODE, (OPEN) LOCATING-DOMINATING SET and METR…
Strong edge-colouring of sparse planar graphs
Julien Bensmail, Ararat Harutyunyan, Hervé Hocquard +1
A strong edge-colouring of a graph is a proper edge-colouring where each colour class induces a matching. It is known that every planar graph with maximum degree has a strong e…
Identifying codes in line graphs
Florent Foucaud, Sylvain Gravier, Reza Naserasr +2
An identifying code of a graph is a subset of its vertices such that every vertex of the graph is uniquely identified by the set of its neighbours within the code. We study the edg…
Extremal graphs for the identifying code problem
Florent Foucaud, Eleonora Guerrini, Matjaz Kovse +3
An identifying code of a graph G is a dominating set C such that every vertex x of G is distinguished from all other vertices by the set of vertices in C that are at distance at mo…