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 K4-minor-free graphs and edge-colorings of 2k-regular K4-minor-free multigraphs. Discrete Applied Mathematics 261:40-51, 2019.
    • M. Chen. R. Naserasr. The optimal routing of Augmented cubes. Information Processing Letters, 136 (2018), 59-63.
  • 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 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):
    • 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.