Research interests: graph theory (algorithms and structure), theoretical computer science.

PhD Students

• Simon Dreyer (2024-) - co-supervised with A. Pinlou

• Hoang La (2019-2022), 2-distance coloring of sparse graphs - co-supervised with M. Montassier and A. Pinlou

• Sarah Blind (2017-2019), Output-sensitive algorithms for enumeration problems in graphs - co-supervised with N. Creignou, K. Knauer and F. Olive

Publications

• S. Cambie, F. Dross, K. Knauer, H. La, P. Valicov, Partitions of planar (oriented) graphs into a connected acyclic and an independent set.
  Submitted

• H. La, P. Valicov, Computer assisted discharging procedure on planar graphs: application to 2-distance coloring.
  Submitted
  Source code : https://gite.lirmm.fr/discharging/planar-graphs

• K. Knauer, H. La, P. Valicov, Feedback vertex sets in (directed) graphs of bounded degeneracy or treewidth.
  Electronic Journal of Combinatorics, Volume 29 (4), 2022.

• F. Foucaud, H. Hocquard, S. Mishra, N. Narayanan, R. Naserasr, É. Sopena, P. Valicov, Exact square coloring of subcubic planar graphs.
  Discrete Applied Mathematics, Volume 293, Pages 74-89, 2021

• H. La, M. Montassier, A. Pinlou, P. Valicov, r-hued (r+1)-coloring of planar graphs with girth at least 8.
  European Journal of Combinatorics, Volume 91, 2021

• S. Blind, K. Knauer, P. Valicov, Enumerating k-arc-connected orientations.
  Algorithmica, Volume 82, Pages 3588-3603, 2020

• K. Knauer, P. Valicov, Cuts in matchings of 3-connected cubic graphs.
  European Journal of Combinatorics, Volume 76, Pages 27-36, 2019.

• F. Foucaud, G. Mertzios, R. Naserasr, A. Parreau, P. Valicov, Identification, location-domination and metric dimension on interval and permutation graphs. I. Bounds. Theoretical Computer Science, Volume 668, Pages 43–58, 2017

• F. Foucaud, G. Mertzios, R. Naserasr, A. Parreau, P. Valicov, Identification, location-domination and metric dimension on interval and permutation graphs. II. Algorithms and complexity. Algorithmica, Volume 78 (3), Pages 914--944, 2017

• K. Knauer, P. Valicov, P. Wenger, Planar digraphs without large acyclic sets.
  Journal of Graph Theory, Volume 85 (1), Pages 288–291, 2017

• J. Bensmail, A. Lagoutte, P. Valicov, Strong edge-coloring of (3, Δ)-bipartite graphs.
  Discete Mathematics, Volume 339 (1), Pages 391–398, 2016.

• V. Borozan, G.J. Chang, N. Cohen, S. Fujita, N. Narayanan, R. Naserasr, P. Valicov, From edge-coloring to strong edge-coloring.
  Electronic Journal of Combinatorics, Volume 22 (2), 2015.

• J. Bensmail, A. Harutyunyan, H. Hocquard, P. Valicov, Strong edge-colouring of sparse planar graphs.
  Discrete Applied Mathematics, Volume 179, Pages 229–234, 2014.

• H. Hocquard, M. Montassier, A. Raspaud, P. Valicov, On strong edge-colouring of subcubic graphs.
  Discrete Applied Mathematics, Volume 161 (16–17), Pages 2467–2479, 2013.

• H. Hocquard, P. Ochem, P. Valicov, Strong edge-colouring and induced matchings.
  Information Processing Letters, Volume 113 (19-21), Pages 836–843, 2013.

• F. Foucaud, S. Gravier, R. Naserasr, A. Parreau, P. Valicov, Identifying codes in line graphs.
  Journal of Graph Theory, Volume 73 (4), pages 425–448, 2013.

• H. Hocquard, P. Valicov, Strong edge colouring of subcubic graphs.
  Discrete Applied Mathematics, Volume 159 (15), Pages 1650–1657, 2011.

• C. Joncour, A. Pêcher, P. Valicov, MPQ-trees for the orthogonal packing problem.
  Journal of Mathematical Modelling and Algorithms, Volume 11 (1), Pages 3–22, 2011.
  Software implementing the algorithm to solve the multidemensional orthogonal packing problem : AlgoKP

• F. Foucaud, E. Guerrini, M. Kovše, R. Naserasr, A. Parreau, P. Valicov, Extremal graphs for the identifying code problem.
  European Journal of Combinatorics, Volume 32 (4), Pages 628–638, 2011.

Conferences with refereed proceedings

• F. Foucaud, S. Mishra, N. Narayanan, R. Naserasr, P. Valicov, Cliques in exact distance powers of graphs of given maximum degree.
  Proceedings of the 11th Latin and American Algorithms, Graphs and Optimisation Symposium (LAGOS 2021), Procedia Computer Science 195:427–436, 2021.

• F. Foucaud, G. Mertzios, R. Naserasr, A. Parreau, P. Valicov, Algorithms and complexity for metric dimension and location-domination on interval and permutation graphs. Proceedings of the 41st International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2015).
  Lecture Notes in Computer Science 9224:456-471, 2016. [arXiv (full manuscript)]

• F. Foucaud, S. Gravier, R. Naserasr, A. Parreau, P. Valicov, Edge-identifying codes (identifying codes in line graphs).
  Eurocomb'11, Budapest, Hungary

• H. Hocquard, P. Ochem, P. Valicov, Bounds and complexity results for strong edge colouring of subcubic graphs.
  Eurocomb'11, Budapest, Hungary

• C. Joncour, A. Pêcher, P. Valicov, MPQ-trees for orthogonal packing problem.
  ISCO 2010, Tunisia, Electronic Notes in Discrete Mathematics, Volume 36, 1 August 2010, Pages 423-429

Manuscripts

• P. Valicov, (2,3)-bipartite graphs are strongly 6-edge-choosable. Manuscript, 2018

• F. Foucaud, R. Naserasr, A. Parreau, P. Valicov, On powers of interval graphs and their orders. Manuscript, 2015

• F. Foucaud, A. Parreau, P. Valicov. Locally identifying colouring planar graphs of small maximum degree and girth 5 with four colours is NP-hard. Manuscript, 2011

• PhD thesis, On packing, colouring and identification problems, 2012.