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.
  • 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.
  • 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 C2ℓ+1-critical graphs of odd-girth 2k + 1. Discrete Applied Mathematics, 319 (2022), 564–575.
    • 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-4-critical signed graphs. Journal of Combinatorial Series B, 153 (2022) 81-104.
    • 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.
  • 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 t-trees and edge-coloring of partial 3-trees. Journal of Combinatorial Series B, 145 (2020) 1-31. [DOI] [PDF]
    • 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 K4-subdivisions. Journal of Combinatorial Mathematics and Combinatorial Computing, 116 (2020), 27–51. [PDF]
    • 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 K4-minor-free graphs and edge-colourings of 2k-regular K4-minor-free multigraphs. Discrete Applied Mathematics 261 (2019) 40-51. [DOI] [PDF]
    • 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.

======================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 C2l+1-critical graphs of odd-girth 2k+1. Proceedings of 6th International Conference on Algorithms and Discrete Applied Mathematics (CALDAM 2020). Lecture Notes in Computer Science 12016:184-196, 2020.
  • 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.
  • 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.
  • Contributed talks at conferences:
    • R. Xu. Homomorphism of K4-minor free graphs. Midsummer Combinatorial Workshop XXIV July 29 - August 2, 2019, Prague, Czech Republics.
    • 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 K4-Subdivisions. 2018 Winter International Graph Theory Workshop, Jinhua,, China.
  • 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.