43 citations · 161 across the 15 of their papers we have counts for
11 papers · 1 filter
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…
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…
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…
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…