Site

## Publication And Conferences

For project members: please do not forget to acknowledge the support from ANR in your publications.

Examples of acknowledgement:

**This work is supported by the ANR project HOSIGRA (ANR-17-CE40-0022).****This work is partially supported by the ANR project HOSIGRA (ANR-17-CE40-0022).**

List of the papers written with support of this project is as follows:

=================**Published journal papers**==============

**2024**---------------------------------------------------- Pavan P D, E. Sopena.
**On the oriented achromatic number of graphs**, Discrete Applied Mathematics 347 (2024), 48--61. [DOI] - M. Habib, L. Mouatadid, E. Sopena, M. Zou.
**(α,β)-Modules in Graphs.**SIAM J. Discrete Math.38(2024), no.1, 566–589. - C. Cappello, R. Naserasr, E. Steffen, and Z. Wang.
**Critically 3-frustrated signed graphs**. To appear in Discrete mathematics. - J. Li, R. Naserasr, Z. Wang, and X. Zhu.
**Circular flows in mono-directed signed graphs**. To appear in Journal of Graph Theory. - R. Naserasr, W. Yu.
**On the packing number of antibalanced signed simple planar graphs of negative girth at least 5**. To appear in Journal of Combinatorial Optimization.

- Pavan P D, E. Sopena.
**2023**---------------------------------------------------- Y. Bai, P. P. Cortés, R. Naserasr, D. A. Quiroz.
**Characterizing and recognizing exact-distance squares of graphs**, to appear in Discrete Mathematics. - M. Bonamy, T. Pierron, E. Sopena.
**Every planar graph with Δ⩾8 is totally (Δ+2)-choosable.**Journal of Graph Theory 104-1 (2023), 17-86. [DOI] - J. Bensmail, H. Hocquard, D. Lajou, E. Sopena.
**A proof of the Multiplicative 1-2-3 Conjecture**. Combinatorica 43, 37-55 (2023). [DOI] - P. Charbit, M. Habib, L. Mouatadid, R. Naserasr.
**A new graph parameter to measure linearity**. Journal of Graph Theory 103 (2023) 462 - 485. - C. Duffy , F. Jacques , M. Montassier , A. Pinlou.
**The chromatic number of 2-edge-colored and signed graphs of bounded maximum degree**. Discrete Mathematics, 2023, 346 (10), pp.113579. - F. Foucaud, R. Naserasr, R. Xu.
**Extended Double Covers and Homomorphism Bounds of Signed Graphs**. The Electronic Journal of Combinatorics, Volume 30, Issue 3, 2023, Paper No.3.31, 22 pp. - P. Haxell, R. Naserasr.
**A note on $\Delta$-critical graphs**. Graphs and Combinatorics 39 (2023) Paper No. 101, 9 pp. - F. Kardos, J. Narboni, R. Naserasr, Z. Wang.
**Circular (4-\epsilon)-coloring of signed graphs**. SIAM Journal on Discrete Mathematics 37 (2023) 1198-1211. - R. Naserasr, W. Yu.
**Packing signatures in signed graphs.**SIAM Journal on Discrete Mathematics 37 (2023) 2365-2381. - R. Naserasr, Z. Wang.
**Signed bipartite circular cliques and a bipartite analogue of Grötzsch's theorem**. Discrete Mathematics 346 (2023) Paper No. 113604, 12 pp. - R. Naserasr, W. Yu.
**Separating signatures in signed planar graphs**. Discrete applied Mathematics 338 (2023) 302-310. - R. Naserasr., R. Skrekovski, Z. Wang, R. Xu.
**Mapping sparse signed graphs to $(K_{2k}, M)$**. Journal of Graph Theory, 104 (2023) 611 - 644.

- Y. Bai, P. P. Cortés, R. Naserasr, D. A. Quiroz.
**2022**---------------------------------------------------- P. Aboulker, G. Aubian, P. Charbit.
**Decomposing and colouring some locally semicomplete digraphs**. European Journal of Combinatorics, 2022, 106, pp.103591. - L. Beaudou, F. Foucaud. R. Naserasr.
**Smallest C**Discrete Applied Mathematics, 319 (2022), 564–575._{2ℓ+1}-critical graphs of odd-girth*2k + 1*. - F. Foucaud, H. Hocquard, D. Lajou, V. Mitsou, T. Pierron.
**Graph Modification for Edge-Coloured and Signed Graph Homomorphism Problems: Parameterized and Classical Complexity**. Algorithmica, 2022, 84 (5), pp.1183-1212. - D. Lajou.
**On Cartesian products of signed graphs.**Discrete Applied Mathematics 319 (2022), 533-555. [DOI] - J. Bensmail, S. Das, S. Nandi, T. Pierron, S. Sen, E. Sopena.
**On the signed chromatic number of some classes of graphs**. Discrete Mathematics, 2022, 345 (2), pp.112664. - J. Bensmail, F. Dross, N. Oijid, E. Sopena.
**Generalising the achromatic number to Zaslavsky's colourings of signed graphs**. Theoretical Computer Science 923 (2022), 196-221. [DOI] - J. Bensmail, H. Hocquard, P.M. Marcille.
**Going Wide with the 1-2-3 Conjecture**. Discrete Applied Mathematics, 2022, 320, pp.15-32. - J. Bensmail, H. Hocquard, D. Lajou, E. Sopena.
**On a List Variant of the Multiplicative 1-2-3 Conjecture**. Graphs and Combinatorics 38 (2022), paper no. 88. [DOI] - F. Jacques , A. Pinlou.
**The chromatic number of signed graphs with bounded maximum average degree**. Discrete Applied Mathematics, 2022, 316 (C), pp.43-59. - X. H. La.
**2-Distance List (Δ+3) -Coloring of Sparse Graphs**. Graphs and Combinatorics, 2022, 38 (6), pp.#167. - X. H. La, B. Lužar, K. Štorgel.
**Further extensions of the Grötzsch Theorem**. Discrete Mathematics, 2022, 345 (6), pp.#112849. - X. H. La, M. Montassier.
**2-Distance list (Δ+2)-coloring of planar graphs with girth at least 10**. Journal of Combinatorial Optimization, 2022, 44 (2), pp.1356-1375. - R. Naserasr, L.A. Pham, Z. Wang.
**Density of C**. Journal of Combinatorial Series B, 153 (2022) 81-104._{-4}-critical signed graphs - R. Naserasr, L.A. Pham.
**Complex and homomorphic chromatic number of signed planar simple graphs**. Graphs and Combinatorics, 38 (2022), no. 3, Paper No. 58, 22 pp.

- P. Aboulker, G. Aubian, P. Charbit.
**2021**---------------------------------------------------- F. Jacques and P. Ochem. "Homomorphisms of planar (m,n)-colored-mixed graphs to planar targets". Discrete Math. 344(12) (2021), 112600.
- P. Aboulker, P. Charbit, R. Naserasr.
**Extension of Gyarfas-Sumner conjecture to digraphs**. The Electronic Journal of Combinatorics, Volume 28, Issue 2, 2021, Paper No. 2.27, 19 pp. [DOI] [Link] - J. Bensmail, S. Das, S. Nand, S. Paul, T. Pierron, S. Sen, E. Sopena.
**Pushable chromatic number of graphs with degree constraints**. Discrete Mathematics, 2021, 344 (1), pp.112151. - M. Bonamy, N. Bousquet, K.K. Dabrowski, M. Johnson, D. Paulusma, T. Pierron.
**Graph Isomorphism for (H1, H2)-Free Graphs: An Almost Complete Dichotomy.**Algorithmica 83 (2021), no. 3, 822–852. - C. J. Casselgren, J. Granholm, A. Raspaud.
**A note on adaptable choosability and choosability with separation of planar graphs.**Journal of Combinatorial Mathematics and Combinatorial Computing , to appear. - C. J. Casselgren, J. Granholm, A. Raspaud.
**On star edge colorings of bipartite and subcubic graphs.**Discrete Applied Mathematics, 298 (2021) 21-33. - P. Charbit, G. Hahn,, M. Kaminski, M. Lafond, N. Lichiardopol, R. Naserasr, B. Seamone, R. Sherkati.
**Edge clique covers in graphs with independence number two**. Journal of Graph Theory, 97(2), (2021) 324-339. [DOI] [PDF] - L. Feuilloley, M. Habib,
**Graph classes and forbidden patterns on three vertices**. SIAM J. Discrete Math. 35 (2021), no. 1, 55–90. - F. Foucaud, B. Gras, A. Perez and F. Sikora.
**On the complexity of broadcast domination and multipacking in digraphs**. Algorithmica, to appear. - F. Foucaud, H. Hocquard and D. Lajou.
**Complexity and algorithms for injective edge-coloring in graphs**. Information Processing Letters 170:106121, 2021. - F. Foucaud, H. Hocquard, S. Mishra, N. Narayanan, R. Naserasr, E. Sopena, P. Valicov.
**Exact square coloring of subcubic planar graphs**. Discrete Applied Mathematics, 293 (2021), 74–89. [DOI] [PDF] - F. Jacques.
**On the chromatic numbers of signed triangular and hexagonal grids**. Information Processing Letters, 2021, 172, pp.#106156. - F. Kardoš, J. Narboni.
**On the 4-color theorem for signed graphs.**European Journal of Combinatorics, 91 (2021), 103215. - A. Kostochka, A. Raspaud, J. Xu.
**Injective edge coloring of graphs with given maximum degree.**European Journal of Combinatorics, to appear. - X. H. La, M. Montassier, A. Pinlou, P. Valicov.
**r-hued (r + 1) -coloring of planar graphs with girth at least 8 for r ≥ 9**. European Journal of Combinatorics, 2021, 91, pp.#103219. - R. Naserasr, E. Sopena, T. Zaslavsky.
**Homomorphisms of signed graphs: an update**. European Journal of Combinatorics, 91 (2021), 103222. [DOI] [PDF] - R. Naserasr, Z. Wang, X. Zhu.
**Circular Chromatic Number of Signed Graphs**. The Electronic Journal of Combinatorics, Volume 28, Issue 2, 2021, Paper No. 2.44, 40 pp. [DOI] [Link]

**2020**-------------------------------------------------------- I. Choi, F. Dross, and P. Ochem. "Partitioning sparse graphs into an independent set and a graph with bounded size components". Discrete Math. 343(8) (2020), 111921.
- R. Belmonte , M. Lampis , V. Mitsou.
**Parameterized (Approximate) Defective Coloring**. SIAM Journal on Discrete Mathematics, 2020, 34 (2), pp.1084-1106. - C. Charpentier, R. Naserasr, E. Sopena.
**Homomorphisms of sparse signed graphs**. The Electronic Journal of Combinatorics, Volume 27, Issue 3, 2020, Paper No. 3.6. [DOI] [LINK] - M. Chen, R. Naserasr.
**Homomorphisms of partial**Journal of Combinatorial Series B, 145 (2020) 1-31. [DOI] [PDF]*t*-trees and edge-coloring of partial 3-trees. - I. Choi , F. Dross , P. Ochem.
**Partitioning sparse graphs into an independent set and a graph with bounded size components**. Discrete Mathematics, 2020, 343 (8), pp.111921. - D. Gonçalves , M. Montassier , A. Pinlou.
**Acyclic coloring of graphs and entropy compression method**. Discrete Mathematics, 2020, 343 (4), pp.#111772. - F. Dross, F. Foucaud, V. Mitsou, P. Ochem, T. Pierron.
**Complexity of homomorphisms of planar signed graphs to cycles.**Discrete Applied Mathematics 284:166-178, 2020. - J. Dybizbanski, P. Ochem, A. Pinlou, and A. Szepietowski.
**Oriented cliques and colorings of graphs with low maximum degree**. Discrete Math. 343 (2020), no. 5, 111829. - F. Foucaud, S. Heydarshahi, A. Parreau.
**Domination and location in twin-free digraphs**. Discrete Applied Mathematics, 2020, 284, pp.42-52. - J. I. Kokkala, K. Meagher, R. Naserasr, K. J. Nurmela, P. R. J. Östergård, and B. Stevens.
**On the Structure of Small Strength-2 Covering Arrays.**Journal of Combinatorial Designs 28(1) (2020) 5-24. [DOI] [PDF] - R. Naserasr, S. Sen, E. Sopena.
**The homomorphism order of signed graphs**. Journal of Combinatorial Mathematics and Combinatorial Computing, 116 (2020), 169–182. [PDF] - R. Naserasr, Z. Wang.
**Bounding signed series-parallel graphs and cores of signed**. Journal of Combinatorial Mathematics and Combinatorial Computing, 116 (2020), 27–51. [PDF]*K*-subdivisions_{4} - M. Bonamy, P. Charbit, O. Defrain, G. Joret, A. Lagoutte, V. Limouzy, L. Pastor, J. Sereni.
**Revisiting a theorem by Folkman on graph colouring.**Electron. J. Combin. 27 (2020), no. 1, Paper No. 1.56, 11 pp.

*'2019*------------------------------------------------------- J. Bensmail.
**On the 2-edge-coloured chromatic number of grids**. Australasian Journal of Combinatorics, 75(3):365-384, 2019. - L. Beaudou, F. Foucaud, R. Naserasr.
**Homomorphism bounds of signed bipartite**. Discrete Applied Mathematics 261 (2019) 40-51. [DOI] [PDF]*K*-minor-free graphs and edge-colourings of_{4}*2k*-regular*K*-minor-free multigraphs_{4} - M. Chen, R. Naserasr.
**The optimal routing of Augmented cubes**. Information processing letter, 136 (2018) 59-63. [DOI] [PDF] - F. Dross, M. Montassier, and A. Pinlou.
**A lower bound on the order of the largest induced linear forest in triangle-free planar graphs**, Discrete Mathematics, vol. 342, pp. 943-950, 2019. - F. Dross, M. Montassier, and A. Pinlou.
**Large induced forests in planar graphs with girth 4**, Discrete Applied Mathematics, vol. 254, pp. 96-106, 2019. - F. Dross and P. Ochem.
**Vertex partitions of (C3,C4,C6)-free planar graphs**. Discrete Mathematics 342(11):3229-3236, 2019. - O. Etesami, N. Ghareghani, M. Habib, M. Hooshmandasl, R. Naserasr, P. Sharifani.
**When an optimal dominating set with given constraints exists**. Theoretical Computer Science 780 (2019) 54-65. [DOI] [PDF] - D. Lajou.
**On the achromatic number of signed graphs.**Theoretical Computer Science, 759 (2019), 50-60. - F. Ramezani,
**Coloring problem of signed interval graphs.**Transactions on Combinatorics, Transactions on Combinatorics, Vol. 8 No. 3 (2019), pp. 29-37.

- J. Bensmail.

======================Published conference papers=====================

- F. Jacques, A. Pinlou.
**The Chromatic Number of Signed Graphs with Bounded Maximum Average Degree**. EuroComb 2021 - European Conference on Combinatorics, Graph Theory and Applications, Sep 2021, Barcelona (online), Spain. pp.657-662. - R. Naserasr, Z. Wang.
**Circular coloring of signed bipartite planar graphs.**EUROCOMB'21, Barcelona (online). [PDF] - F. Foucaud, S. Mishra, Narayanan N, R. Naserasr and P. Valicov.
**Cliques in exact distance powers of graphs of given maximum degree.**Proceedings of LAGOS 2021, to appear. - S. Laplante , R. Naserasr, and A. Sunny.
**Sensitivity Lower Bounds from Linear Dependencies.**LIPIcs, Volume 170, MFCS 2020. - D. Chakraborty, S. Das, F. Foucaud, H. Gahlawat, D. Lajou and B. Roy.
**Complexity and algorithms for geodetic set in planar graphs and chordal graphs**. Proceedings of the 31st International Symposium on Algorithms and Computation (ISAAC 2020), Leibniz International Proceedings in Informatics 181,7:1-7:15, 2020. - S. Dey, F. Foucaud, S. C. Nandy and A. Sen.
**Discriminating codes in geometric setups**. Proceedings of the 31st International Symposium on Algorithms and Computation (ISAAC 2020), Leibniz International Proceedings in Informatics 181,24:1-24:16, 2020. - F. Foucaud, B. Gras, A. Perez and F. Sikora.
**On the complexity of broadcast domination and multipacking in digraphs**. Proceeedings of the 31st International Workshop on Combinatorial Algorithms (IWOCA 2020). Lecture Notes in Computer Science 12126:264-276, 2020. - F. Foucaud, R. Klasing, M. Miller and J. Ryan.
**Monitoring the edges of a graph using distances**. Proceedings of the 6th International Conference on Algorithms and Discrete Applied Mathematics (CALDAM 2020). Lecture Notes in Computer Science 12016:28-40, 2020. - D. Lajou.
**On Cartesian products of signed graphs**. Proceedings of the 6th International Conference on Algorithms and Discrete Applied Mathematics (CALDAM 2020). Lecture Notes in Computer Science 12016:219-234, 2020. - D. Chakraborty, F. Foucaud, H. Gahlawat, S. K. Ghosh and B. Roy.
**Hardness and approximation for the geodetic set problem in some graph classes**. Proceedings of the 6th International Conference on Algorithms and Discrete Applied Mathematics (CALDAM 2020). Lecture Notes in Computer Science 12016:102-115, 2020. - L. Beaudou, F. Foucaud, R. Naserasr.
**Smallest C**Proceedings of 6th International Conference on Algorithms and Discrete Applied Mathematics (CALDAM 2020). Lecture Notes in Computer Science 12016:184-196, 2020._{2l+1}-critical graphs of odd-girth 2k+1. - F. Jacques, M. Montassier, and A. Pinlou.
**The chromatic number and switching chromatic number of 2-edge-colored graphs of bounded degree**. 5th Bordeaux Graph Workshop, 2019. - D. Lajou.
**Parameterized complexity of modification problems on edge-coloured and signed graph homomorphisms**. 5th Bordeaux Graph Workshop, 2019. - Rémy Belmonte, Eun Jung Kim, Michael Lampis, Valia Mitsou, Yota Otachi, and Florian Sikora.
**Token Sliding on Split Graphs.**In proceedings of 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019). LIPIcs series, DOI: 10.4230/LIPIcs.STACS.2019.13, pages 13:1--13:17. - F. Foucaud, H. Hocquard, D. Lajou, V. Mitsou, T. Pierron.
**Parameterized complexity of edge-coloured and signed graph homomorphisms.**14th International Symposium on Parameterized and Exact Computation, IPEC 2019, Munich, Germany, September 11–13, 2019. - L. Beaudou, F. Foucaud, F. Madelaine, L. Nourine, G. Richard.
**Complexity of conjunctive regular path query homomorphisms.**Proceedings of*Computability in Europe 2019*, Lecture Notes in Computer Science 11558:108-119, 2019.

- F. Jacques, A. Pinlou.

- Invited talks at conferences:
- E. Sopena.
**Recent Developments on Homomorphisms and Colourings of Signed Graphs.**Colourings, Independence and Domination, 18th workshop on Graph Theory, CID'19, Piechowice, Poland, September 15-20, 2019. - R. Naserasr.
**Homomorphisms of sparse signed graphs.**4th Macedonian Workshop on Graph Theory and Applications, 26-30 August 2019, Ohrid Macedonia. - R. Naserasr.
**Homomorphisms of signed graphs.**2018 Winter International workshop on Graph theory, Jinhua, China.

- E. Sopena.
- Contributed talks at conferences:
- R. Xu.
**Homomorphism of K**Midsummer Combinatorial Workshop XXIV July 29 - August 2, 2019, Prague, Czech Republics._{4}-minor free graphs. - R. Naserasr.
**Homomorphisms of signed graphs.**Midsummer Combinatorial Workshop XXIV, at Gena and Robert Day. August 5, 2019, Prague, Czech Republics. - Z. Wang.
**Cores of Signed K**2018 Winter International Graph Theory Workshop, Jinhua,, China._{4}-Subdivisions.

- R. Xu.
- Submitted (to journals or conferences):
- S. Dey, F. Foucaud, S. C. Nandy and A. Sen.
**Discriminating codes in geometric setups**. - D. Chakraborty, S. Das, F. Foucaud, H. Gahlawat, D. Lajou and B. Roy.
**Complexity and algorithms for geodetic set in planar graphs and chordal graphs**. - F. Foucaud, S. Kao, R. Klasing, M. Miller and J. Ryan.
**Monitoring the edges of a graph using distances**.

- S. Dey, F. Foucaud, S. C. Nandy and A. Sen.