**Research papers**-

**Theses**-

**Other material**

# Research papers

- Dibyayan Chakraborty, Antoine Dailly, Sandip Das, FF, Harmender Gahlawat and Subir Kumar Ghosh.
Manuscript, 2022. [HAL]*Complexity and algorithms for ISOMETRIC PATH COVER on chordal graphs and beyond.*

- Maël Dumas, FF, Anthony Perez and Ioan Todinca.
Manuscript, 2022. [arXiv]*On graphs coverable by k shortest paths.*

- Subhadeep R. Dev, Sanjana Dey, FF, Ralf Klasing and Tuomo Lehtilä.
Manuscript, 2022. [arXiv]*The RED-BLUE SEPARATION problem on graphs.**A preliminary conference version was presented at IWOCA 2022.*

- FF and Tuomo Lehtilä.
Manuscript, 2022. [arXiv]*Bounds and extremal graphs for total dominating identifying codes.*

- Laurent Beaudou, Caroline Brosse, Oscar Defrain, FF, Aurélie Lagoutte, Vincent Limouzy and Lucas Pastor.
Manuscript, 2021. [arXiv | HAL]*Connected greedy colourings of perfect graphs and other classes: the good, the bad and the ugly.*

- FF, Reza Naserasr and Rongxing Xu.
Manuscript, 2021. [arXiv | HAL]*Extended Double Covers and homomorphism bounds of signed graphs.* - Sanjana Dey, FF, Subhas C. Nandy and Arunabha Sen.
Manuscript, 2021. [arXiv]*Complexity and approximation for discriminating and identifying code problems in geometric setups.**A preliminary conference version was presented at ISAAC 2020.*

- Dibyayan Chakraborty, Sandip Das, FF, Harmender Gahlawat, Dimitri Lajou and Bodhayan Roy.
Manuscript, 2021. [arXiv]*Algorithms and complexity for geodetic sets on planar and chordal graphs.*

*A preliminary conference version was presented at ISAAC 2020.*

- FF and Tuomo Lehtilä.
*Revisiting and improving upper bounds for identifying codes.**SIAM Journal on Discrete Mathematics*, accepted (subject to minor revisions). [arXiv]

- FF.
*Problems related to a conjecture on location-domination in twin-free graphs.**Indian Journal of Discrete Mathematics*8(1), 2022. [HAL]

### 2022

- Laurent Beaudou, FF and Reza Naserasr.
*Smallest C2l+1-critical graphs of odd-girth 2k+1.**Discrete Applied Mathematics*319:564-575, 2022.*Special issue for CALDAM 2020.*[PDF | arXiv | www]

*A preliminary conference version was presented at CALDAM 2020.*

- FF, Shih-Shun Kao, Ralf Klasing, Mirka Miller and Joe Ryan.
*Monitoring the edges of a graph using distances.**Discrete Applied Mathematics*319:424-438, 2022.*Special issue for CALDAM 2020.*[PDF | HAL | arXiv | www]

*A preliminary conference version was presented at CALDAM 2020.*

- [J38] FF, Hervé Hocquard, Dimitri Lajou, Valia Mitsou and Théo Pierron.
*Graph modification for edge-coloured and signed graph homomorphism problems: parameterized and classical complexity.**Algorithmica*84(5):1183-1212, 2022. [PDF | HAL | arXiv | www]

*A preliminary conference version was presented at IPEC 2019.*

- [C18] Subhadeep R. Dev, Sanjana Dey, FF, Ralf Klasing and Tuomo Lehtilä.
Proceedings of the 33rd International Workshop on Combinatorial Algorithms (IWOCA 2022),*The RED-BLUE SEPARATION problem on graphs.**Lecture Notes in Computer Science*13270:285-298, 2022. [PDF | HAL | www]

### 2021

- [J37] FF, Benjamin Gras, Anthony Perez and Florian Sikora.
*On the complexity of BROADCAST DOMINATION and MULTIPACKING in digraphs.**Algorithmica*83(9):2651-2677, 2021.*Special issue for selected papers of IWOCA 2020.*[PDF | arXiv | www]

*A preliminary conference version was presented at IWOCA 2020.*

- [J36] FF, Narges Ghareghani, Aida Roshany-Tabrizi and Pouyeh Sharifani.
*Characterizing extremal graphs for open neighbourhood location-domination.**Discrete Applied Mathematics*302:76-79, 2021. [PDF | arXiv | www] - [J35] FF, Hervé Hocquard and Dimitri Lajou.
*Complexity and algorithms for injective edge-coloring in graphs.**Information Processing Letters*170:106121, 2021. [PDF | HAL | arXiv | www] - [J34] FF, Hervé Hocquard, Suchismita Mishra, Narayanan Narayanan, Reza Naserasr, Éric Sopena and Petru Valicov.
*Exact square coloring of subcubic planar graphs.**Discrete Applied Mathematics*293:74-89, 2021. [PDF | HAL | arXiv | www] - [C17] FF, Suchismita Mishra, Narayanan Narayanan, Reza Naserasr and Petru Valicov.
Proceedings of the 11th Latin and American Algorithms, Graphs and Optimisation Symposium (LAGOS 2021),*Cliques in exact distance powers of graphs of given maximum degree.**Procedia Computer Science*195:427-436, 2021. [PDF | HAL | www] - [J33] François Dross, FF, Valia Mitsou, Pascal Ochem and Théo Pierron.
*Complexity of planar signed graph homomorphisms to cycles.**Discrete Applied Mathematics*284:166-178, 2020. [PDF | HAL | arXiv | www] - [J32] FF, Shahrzad Heydarshahi and Aline Parreau.
*Domination and location in twin-free digraphs.**Discrete Applied Mathematics*284:42-52, 2020. [PDF | HAL | arXiv | www] - [C16] Dibyayan Chakraborty, Sandip Das, FF, Harmender Gahlawat, Dimitri Lajou and Bodhayan Roy.
Proceedings of the 31st International Symposium on Algorithms and Computation (ISAAC 2020),*Algorithms and complexity for geodetic sets on planar and chordal graphs.**Leibniz International Proceedings in Informatics*181,7:1-7:15, 2020. [PDF | www]*The full version is submitted to a journal.* - [C15] Sanjana Dey, FF, Subhas C. Nandy and Arunabha Sen.
Proceedings of the 31st International Symposium on Algorithms and Computation (ISAAC 2020),*Discriminating codes in geometric setups.**Leibniz International Proceedings in Informatics*181,24:1-24:16, 2020. [PDF | www]*The full version is submitted to a journal.* - [C14] FF, Benjamin Gras, Anthony Perez and Florian Sikora.
Proceedings of the 31st International Workshop on Combinatorial Algorithms (IWOCA 2020),*On the complexity of BROADCAST DOMINATION and MULTIPACKING in digraphs.**Lecture Notes in Computer Science*12126:264-276, 2020. [PDF | www]*The full version appeared in the journal*Algorithmica*in 2021.* - [C13] Dibyayan Chakraborty, FF, Harmender Gahlawat, Subir Kumar Ghosh and Bodhayan Roy.
Proceedings of the 6th International Conference on Algorithms and Discrete Applied Mathematics (CALDAM 2020),*Hardness and approximation for the geodetic set problem in some graph classes.**Lecture Notes in Computer Science*12016:102-115, 2020. [PDF | arXiv | www] - [C12] FF, Ralf Klasing, Mirka Miller and Joe Ryan.
Proceedings of the 6th International Conference on Algorithms and Discrete Applied Mathematics (CALDAM 2020),*Monitoring the edges of a graph using distances.**Lecture Notes in Computer Science*12016:28-40, 2020. [PDF | HAL | www]*The full version is to appear in the journal*Discrete Applied Mathematics*.* - [C11] Laurent Beaudou, FF and Reza Naserasr.
Proceedings of the 6th International Conference on Algorithms and Discrete Applied Mathematics (CALDAM 2020),*Smallest C2l+1-critical graphs of odd-girth 2k+1.**Lecture Notes in Computer Science*12016:184-196, 2020. [PDF | www]*The full version is to appear in the journal*Discrete Applied Mathematics*.* - [J31] Antoine Dailly, FF and Adriana Hansberg.
*Strengthening the Murty-Simon conjecture on diameter 2 critical graphs.**Discrete Mathematics*342(11):3142-3159, 2019. [PDF | HAL | arXiv | www] - [J30] Laurent Beaudou, Richard C. Brewster and FF.
*Broadcast domination and multipacking: bounds and the integrality gap.**The Australasian Journal of Combinatorics*74(1):86-97, 2019. [PDF | arXiv | www] - [J29] Laurent Beaudou, FF and Reza Naserasr.
*Homomorphism bounds of signed bipartite K4-minor-free graphs and edge-colourings of 2k-regular K4-minor-free multigraphs.**Discrete Applied Mathematics*261:40-51, 2019.*Special issue for the 2016 GO X Meeting.*[PDF | HAL | arXiv | www] - [J28] Cristina Bazgan, FF and Florian Sikora.
*Parameterized and approximation complexity of PARTIAL VC DIMENSION.**Theoretical Computer Science*766:1-15, 2019. [PDF | HAL |arXiv | www]

*A preliminary conference version was presented at COCOA 2016.*

- [C10] FF, Hervé Hocquard, Dimitri Lajou, Valia Mitsou and Théo Pierron.
Proceedings of the 14th International Symposium on Parameterized and Exact Computation (IPEC 2019),*Parameterized complexity of edge-coloured and signed graph homomorphism problems.**Leibniz International Proceedings in Informatics*148,15:1-15:16, 2019. [PDF | www]*The full version appeared in the journal*Algorithmica*in 2022.* - [C9] Laurent Beaudou, FF, Florent Madelaine, Lhouari Nourine and Gaétan Richard.
Proceedings of the 15th Conference on Computability in Europe (CIE 2019),*Complexity of conjunctive regular path query homomorphisms.**Lecture Notes in Computer Science*11558:108-119, 2019. [PDF | www] - [J27] Édouard Bonnet, FF, Eun Jung Kim and Florian Sikora.
*Complexity of Grundy coloring and its variants.**Discrete Applied Mathematics*243:99-114, 2018. [PDF | HAL | arXiv | www]

*A preliminary conference version was presented at COCOON 2015.*

- [J26] Laurent Beaudou, Peter Dankelmann, FF, Michael A. Henning, Arnaud Mary and Aline Parreau.
*Bounding the order of a graph using its diameter and metric dimension: a study through tree decompositions and VC dimension.**SIAM Journal on Discrete Mathematics*32(2):902-918, 2018. [PDF | arXiv | www] - [J25] FF and Ralf Klasing.
*Parameterized and approximation complexity of the detection pair problem in graphs.**Journal of Graph Algorithms and Applications*21(6):1039-1056, 2017. [PDF | arXiv | www] - [J24] FF, Ararat Harutyunyan, Pavol Hell, Sylvain Legay, Yannis Manoussakis and Reza Naserasr.
*The complexity of tropical graph homomorphisms.**Discrete Applied Mathematics*229:64-81, 2017. [PDF | arXiv (enhanced version) | www] - [J23] Laurent Beaudou, FF and Reza Naserasr.
*Homomorphism bounds and edge-colourings of K4-minor-free graphs.**Journal of Combinatorial Theory, Series B*124:128-164, 2017. [PDF | arXiv | www] - [J22] FF, George B. Mertzios, Reza Naserasr, Aline Parreau and Petru Valicov.
*Identification, location-domination and metric dimension on interval and permutation graphs. II. Algorithms and complexity.**Algorithmica*78(3):914-944, 2017. [PDF | arXiv | www]

*A preliminary conference version was presented at WG 2015.*

- [J21] FF, George B. Mertzios, Reza Naserasr, Aline Parreau and Petru Valicov.
*Identification, location-domination and metric dimension on interval and permutation graphs. I. Bounds.**Theoretical Computer Science*668:43-58, 2017. [PDF | arXiv | www] - [J20] Olivier Baudon, Julien Bensmail, FF and Monika Pilśniak.
*Structural properties of recursively partitionable graphs with connectivity 2.**Discussiones Mathematicae Graph Theory*37(1):89-115, 2017. [PDF | HAL | www] - [J19] FF, Guillem Perarnau and Oriol Serra.
*Random subgraphs make identification affordable.**Journal of Combinatorics*8(1):57-77, 2017. [PDF | arXiv | www]

*A preliminary conference version was presented at EUROCOMB 2013.*

- [J18] Richard C. Brewster, FF, Pavol Hell and Reza Naserasr.
*The complexity of signed and edge-coloured graph homomorphisms.**Discrete Mathematics*340(2):223-235, 2017. [PDF | arXiv | www] - [J17] FF and Michael A. Henning.
*Location-domination in line graphs.**Discrete Mathematics*340(1):3140-3153, 2017. [PDF | arXiv | www] - [J16] FF and Michael A. Henning.
*Locating-total dominating sets in twin-free graphs: a conjecture.**The Electronic Journal of Combinatorics*23(3):P3.9, 2016. [PDF | arXiv | www] - [J15] FF and Michael A. Henning.
*Location-domination and matching in cubic graphs.**Discrete Mathematics*339(4):1221-1231, 2016. [PDF | arXiv | www] - [J14] FF, Michael A. Henning, Christian Löwenstein and Thomas Sasse.
*Locating-dominating sets in twin-free graphs.**Discrete Applied Mathematics*200:52-58, 2016. [PDF | arXiv | www] - [C8] Cristina Bazgan, FF and Florian Sikora.
Proceedings of the 10th Annual International Conference on Combinatorial Optimization and Applications (COCOA 2016),*On the approximability of PARTIAL VC DIMENSION.**Lecture Notes in Computer Science*10043:92-106, 2016. [PDF | www]

*The full version appeared in the journal*Theoretical Computer Science*in 2019.* - [J13] Camino Balbuena, FF and Adriana Hansberg.
*Locating-dominating sets and identifying codes in graphs of girth at least 5.**The Electronic Journal of Combinatorics*22(2):P2.15, 2015. [PDF | arXiv | www] - [J12] FF.
*Decision and approximation complexity for identifying codes and locating-dominating sets in restricted graph classes.**Journal of Discrete Algorithms*31:48-68, 2015.*Special issue for selected papers of IWOCA 2013.*[PDF | HAL | www]

*A preliminary conference version was presented at IWOCA 2013.*

- [J11] FF, Michael Krivelevich and Guillem Perarnau.
*Large subgraphs without short cycles.**SIAM Journal on Discrete Mathematics*29(1):65-78, 2015. [PDF | arXiv | www] - [C7] FF, George B. Mertzios, Reza Naserasr, Aline Parreau and Petru Valicov.
Proceedings of the 41st International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2015),*Algorithms and complexity for metric dimension and location-domination on interval and permutation graphs.**Lecture Notes in Computer Science*9224:456-471, 2016. [PDF | HAL | www]

*The full version appeared in the journal*Algorithmica*in 2017.* - [C6] Édouard Bonnet, FF, Eun Jung Kim and Florian Sikora.
Proceedings of the 21st International Conference on Computing and Combinatorics (COCOON 2015),*Complexity of Grundy coloring and its variants.**Lecture Notes in Computer Science*9198:109-120, 2015. [PDF | www]

*The full version appeared in the journal*Discrete Applied Mathematics*in 2018.* - [U2] FF, Reza Naserasr, Aline Parreau and Petru Valicov.
Manuscript, 2015. [arXiv]*On powers of interval graphs and their orders.* - [J10] FF, Ralf Klasing and Peter J. Slater.
*Centroidal bases in graphs.**Networks*64(2):96-108, 2014. [PDF | arXiv | www] - [J9] FF, Tero Laihonen and Aline Parreau.
*An improved lower bound for (1,<=2)-identifying codes in the king grid.**Advances in Mathematics of Communications*8(1):35-52, 2014. [PDF | HAL | arXiv | www] - [J8] Olivier Baudon, FF, Jakub Przybyło and Mariusz Woźniak.
*On the structure of arbitrarily partitionable graphs with given connectivity.**Discrete Applied Mathematics*162:381-385, 2014. [PDF | HAL | www] - [C5] FF and Reza Naserasr.
Proceedings of the 11th Latin American Symposium on Theoretical Informatics (LATIN 2014),*The complexity of signed graph homomorphisms and signed constraint satisfaction.**Lecture Notes in Computer Science*8392:526-537, 2014. [PDF | www] - [J7] FF and Matjaž Kovše.
*Identifying path covers in graphs.**Journal of Discrete Algorithms*23:21-34, 2013.*Special issue for selected papers of IWOCA 2012.*[PDF | HAL | www]

*A preliminary conference version was presented at IWOCA 2012.*

- [J6] FF, Sylvain Gravier, Reza Naserasr, Aline Parreau and Petru Valicov.
*Identifying codes in line graphs.**Journal of Graph Theory*73(4):425-448, 2013. [PDF | HAL | arXiv | www]

*A preliminary conference version was presented at EUROCOMB 2011.*

- [J5] FF, Reza Naserasr and Aline Parreau.
*Characterizing extremal digraphs for identifying codes and extremal cases of Bondy's theorem on induced subsets.**Graphs and Combinatorics*29(3):463-473, 2013. [PDF | HAL | arXiv | www] - [C4] FF, Guillem Perarnau and Oriol Serra.
Proceedings of the 7th European Conference on Combinatorics, Graph Theory and Applications (EUROCOMB 2013),*Random subgraphs make identification affordable.**CRM Series*16:415-420, 2013. [PDF | www]

*The full version appeared in the journal*Journal of Combinatorics*in 2017.* - [C3] FF.
Proceedings of the 24th International Workshop on Combinatorial Algorithms (IWOCA 2013),*The complexity of the identifying code problem in restricted graph classes.**Lecture Notes in Computer Science*8288:150-163, 2013. [PDF | www]

*The full version appeared in the journal*Journal of Discrete Algorithms*in 2015.* - [J4] FF, Ralf Klasing, Adrian Kosowski and André Raspaud.
*On the size of identifying codes in triangle-free graphs.**Discrete Applied Mathematics*160(10-11):1532-1546, 2012. [PDF | HAL | arXiv | www] - [J3]
*Locally identifying colourings for graphs with given maximum degree.**Discrete Mathematics*312(10):1832-1837, 2012. [PDF | HAL | arXiv | www] - [J2] FF and Guillem Perarnau.
*Bounds on identifying codes in terms of degree parameters.**The Electronic Journal of Combinatorics*19:P32, 2012. [PDF | HAL | arXiv | www] - [C2] FF and Matjaž Kovše.
Proceedings of the 23rd International Workshop on Combinatorial Algorithms (IWOCA 2012),*On graph identification problems and the special case of identifying vertices using paths.**Lecture Notes in Computer Science*7643:32-45, 2012. [PDF | www]

*The full version appeared in the journal*Journal of Discrete Algorithms*in 2013.* - [J1] FF, Eleonora Guerrini, Matjaž Kovše, Reza Naserasr, Aline Parreau and Petru Valicov.
*Extremal graphs for the identifying code problem.**European Journal of Combinatorics*32(4):628-638, 2011. [PDF | HAL | arXiv | www] - [C1] FF, Sylvain Gravier, Reza Naserasr, Aline Parreau and Petru Valicov.
Proceedings of the 6th European Conference on Combinatorics, Graph Theory and Applications (EUROCOMB 2011),*Edge identifying codes.**Electronic Notes in Discrete Mathematics*38:343-348, 2011. [PDF | www]

*The full version appeared in the journal*Journal of Graph Theory*in 2013.* - [U1] FF, Aline Parreau and Petru Valicov.
Unpublished manuscript, 2011. [PDF]*Locally identifying colouring planar graphs of small maximum degree and girth 5 with four colours is NP-hard.*

### Submitted

### Accepted

### 2020

### 2019

### 2018

### 2017

### 2016

### 2015

### 2014

### 2013

### 2012

### 2011

# Theses

- FF.
PhD Thesis, defended on December 10th, 2012 at Université Bordeaux 1. Under the supervision of Ralf Klasing and André Raspaud. In English. [Manuscript (Clickable colour PDF) | Manuscript (Printable Black&White PDF) | Slides of the defense (PDF)]*Combinatorial and algorithmic aspects of identifying codes in graphs.* - FF.
. Master's thesis, Université Bordeaux 1, June 2009. Under the supervision of Ralf Klasing and André Raspaud. In English, with French introduction. [Manuscript (PDF)]*Identifying codes in special graph classes*

# Other material

- FF, Leszek A. Gąsieniec, Ralf Klasing, Tomasz Radzik and William F. Smyth.
[PDF]*IWOCA 2020 in Bordeaux (Oops! On-line!).**Bulletin of the EATCS*132:73-76, 2020. [www]*IFIP News*, September 2020, pp. 9-10. [PDF]*IFORS News*, September 2020, pp. 24-25. [PDF] - FF.
IWOCA Open Problem, 2020. [www]*Complexity of MULTIPACKING in graphs.* - FF.
*The complexity of covering a ladder using cycles.*

IWOCA Open Problem, 2012. [www]

**Research papers**-

**Theses**-

**Other material**