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
- 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. Bensmail.
**On the 2-edge-coloured chromatic number of grids**. Australasian Journal of Combinatorics, 75(3):365-384, 2019. - F. Dross and P. Ochem.
**Vertex partitions of (C3,C4,C6)-free planar graphs**. Discrete Mathematics 342(11):3229-3236, 2019. - 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. - O. Etesami, N. Ghareghani, M. Habib, M. Hooshmandasl, R. Naserasr, P. Sharifani.
**When an optimal dominating set with given constraints exists**. Theor. Comput. Sci. 780: 54--65 (2019), - J. I. Kokkala, K. Meagher, R. Naserasr, K. J. Nurmela, P. R. J. Östergård, and Brett Stevens.
**On the Structure of Small Strength-2 Covering Arrays.**J Combin Des. 2019. https://doi.org/10.1002/jcd.21671 - 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. - L. Beaudou, F. Foucaud and R. Naserasr.
**Homomorphism bounds of signed bipartite K**Discrete Applied Mathematics 261:40-51, 2019._{4}-minor-free graphs and edge-colorings of 2k-regular K_{4}-minor-free multigraphs. - M. Chen. R. Naserasr.
**The optimal routing of Augmented cubes.**Information Processing Letters, 136 (2018), 59-63.

- F. Dross, F. Foucaud, V. Mitsou, P. Ochem, T. Pierron.
- Published conference papers:
- 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**. ISAAC 2020, to appear. - S. Dey, F. Foucaud, S. C. Nandy and A. Sen.
**Discriminating codes in geometric setups**. ISAAC 2020, to appear. - 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.

- D. Chakraborty, S. Das, F. Foucaud, H. Gahlawat, D. Lajou and B. Roy.
- 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):
- F. Foucaud, H. Hocquard and D. Lajou.
**Complexity and algorithms for injective edge-coloring in graphs**. - F. Foucaud, S. Mishra, Narayanan N, R. Naserasr and P. Valicov.
**Cliques in exact distance powers of graphs of given maximum degree**. - F. Foucaud, H. Hocquard, S. Mishra, Narayanan N, R. Naserasr, E. Sopena and P. Valicov.
**Exact square coloring of subcubic planar graphs**. - J. Dybizbanski, P. Ochem, A. Pinlou, and A. Szepietowski.
**Oriented cliques and colorings of graphs with low maximum degree**. - R. Naserasr, E. Sopena and T. Zaslavsky.
**Homomorphisms of signed graphs: an update**. - C. Charpentier, R. Naserasr and E. Sopena.
**Homomorphisms of sparse signed graphs**. - P. Charbit, G. Hahn,, M. Kaminski, M. Lafond, N. Lichiardopol, R. Naserasr, B. Seamone and R. Sherkati.
**Edge clique covers in graphs with independence number**. - P. Charbit, M. Habib, L. Mouatadid, and R. Naserasr.
**A New Graph Parameter To Measure Linearity Linear Structure and Graph Classes**. - M. Chen. R. Naserasr.
**Homomorphisms of partial t-trees and edge-coloring of partial 3-trees.** - F. Kardoš, J. Narboni.
**On the 4-color theorem for signed graphs.** - M. Bonamy, N. Bousquet, K.K. Dabrowski, M. Johnson, D. Paulusma, T. Pierron.
**Graph Isomorphism for (H1, H2)-Free Graphs: An Almost Complete Dichotomy.** - M. Bonamy, T. Pierron, E. Sopena.
**Every planar graph with Δ⩾8 is totally (Δ+2)-choosable.** - D. Lajou.
**On Cartesian products of signed graphs.**

- F. Foucaud, H. Hocquard and D. Lajou.