IFCAM=Indo French Centre for Applied Mathematics

This is a collaborative project on Application of GRAph Homomorphisms--> AGRAHO with partners from France and India.

I am the coordinator for French site and Sagnik Sen is the coordinator for Indian site.

Members of project:

French side, senior members:

  • Julien Bensmail,
  • Florent Foucaud,
  • Amélie Gheerbrant,
  • Reza Naserasr (coordinator of French side)
  • Cristina Sirangelo,
  • Eric Sopena,

Indian side, senior:

  • Sandip Das,
  • Subir K. Ghosh,
  • Joydeep Mukherjee,
  • Soumen Nandi
  • Sagnik Sen (coordinator of Indian side)

French side, junior members:

  • Dimitri Lajou,
  • Theo Pierron,
  • Uma kant Sahoo,

Indian side, junior:

  • Dibyayan Chakraborty
  • Arun K. Das
  • Soura S. Das
  • Tapas Das
  • Supraja DK
  • Harmender Gahlawat,
  • Swathy Prabhu,
  • Samim Islam
  • Zin M. Myint
  • Taruni S. Ph.D

Summary of the project:

In this project, we are going to study the graph homomorphism problems from a very general point of view. Apart from studying the usual graph homomorphism on undirected graphs, we will study it for different types of graphs such as, signed graphs, oriented graphs, edge-colored graphs, colored mixed graphs etc. We will apply the theories and techniques associated with graph homomorphism to solve practical problems. Our main application oriented work is studying graph homomorphism in the context of graph database, a type of database now a days used even by popular social medias. Graph homomorphism is equivalent to the query evalution problem in graph database, and thus have exciting intersection with the theory. In our group we have experts of graph homomorphisms as well as graph database making this project a potential case for Indo- French interdeciplinary collaboration. We want to organize a workshop by the end of this project. We also consider a few other application oriented topics as auxiliary research tracks inside this project.


A list of journal publications ordered alphabetically (last updated November 2021):

\bibitem{BFN2019} Laurent Beaudou, Florent Foucaud and Reza Naserasr, {\it Homomorphism bounds of signed bipartite $K_4$-minor-free graphs and edge-colourings of $2k$-regular $K_4$-minor-free multigraphs}, Discrete Applied Mathematics 2019.

\bibitem{BFN21+} Laurent Beaudou, Florent Foucaud and Reza Naserasr, {\it Smallest $C_{2l+1}$-critical graphs of odd-girth $2k+1$}, Disc. Applied Math. to appear.

\bibitem{BENSMAIL2019} Julien Bensmail, {\it On the 2-edge-coloured chromatic number of grids}, Australasian Journal of Combinatorics 2019.

\bibitem{BNRS2021} Julien Bensmail, Soumen Nandi, Mithun Roy, Sagnik Sen. \textit{Enumeration of edge-critical underlying absolute planar cliques for signed graphs}, Austalas. {J} Comb 2021.

\bibitem{BDNPPSS2021-a} Julien Bensmail, Sandip Das, Soumen Nandi, Soumyajit Paul, Th{\'{e}}o Pierron, Sagnik Sen, \'{E}ric Sopena, {\it Pushable chromatic number of graphs with degree constraints}, Discret. Math. 2021.

\bibitem{BDNPSS2021-b} Julien Bensmail, Sandip Das, Soumen Nandi, Th{\'{e}}o Pierron, Sagnik Sen, {\'{E}}ric Sopena. {\it On the signed chromatic number of some classes of graphs}. Discret. Math. 2021 (accepted).

\bibitem{BNRS2020} Julien Bensmail, Soumen Nandi, Mithun Roy, Sagnik Sen, {\it Enumeration of edge-critical underlying absolute planar cliques for signed graphs}, Australas. J. Comb. 2020.

\bibitem{CDFS2021} Dibyayan Chakraborty, Sandip Das, Mathew C. Francis, Sagnik Sen, {\it On rectangle intersection graphs with stab number at most two}, Discret. Appl. Math. 2021.

\bibitem{CDM2021} Dibyayan Chakraborty, Sandip Das, Joydeep Mukherjee, {\it Dominating Set on Overlap Graphs of Rectangles Intersecting a Line}, COCOON, 2019.

\bibitem{CDNRS2021} Dipayan Charaborty, Sandip Das, Soumen Nandi, Debdeep Roy, Sagnik Sen, {\it On Clique numbers of colored mixed graphs}, Discrete Applied Mathematics 2021 (accepted).

\bibitem{DGKS2021} Sandip Das, Harmender Gahlawat, Uma K. Sahoo, Sagnik Sen {\it Cops and Robber on some families of oriented graphs}, Theoretical Computer Science 2021.

\bibitem{DNS2020} Sandip Das, Ayan Nandy, Swami Sarvottamananda, {\it Linear time algorithms for Euclidean 1-center in $R^d$ with non-linear convex constraints}, Discret. Appl. Math. 2020.

\bibitem{DFMOP2020} Francois Dross, Florent Foucaud, Valia Mitsou, Pascal Ochem and Th\'eo Pierron, {\it Complexity of planar signed graph homomorphisms to cycles}, Discrete Applied Mathematics 2020.

\bibitem{FGPS2021} Florent Foucaud, Benjamin Gras, Anthony Perez and Florian Sikora, {\it On the complexity of broadcast domination and multipacking in digraphs}, Algorithmica 2021.

\bibitem{FHL2021} Florent Foucaud, Hervé Hocquard and Dimitri Lajou, {\it Complexity and algorithms for injective edge-coloring in graphs}, Information Processing Letters 2021.

\bibitem{FHMNNSV2021} Florent Foucaud, Hervé Hocquard, Suchismita Mishra, Narayanan Narayanan, Reza Naserasr, \'Eric Sopena and Petru Valicov, {\it Exact square coloring of subcubic planar graphs}, Discrete Applied Mathematics 2021.

\bibitem{FHP2020} Florent Foucaud, Shahrzad Heydarshahi and Aline Parreau, {\it Domination and location in twin-free digraphs}, Discrete Applied Mathematics 2020.

\bibitem{LAJOU2021} Dimitri Lajou, {\it On Cartesian products of signed graphs}, Discrete Applied Mathematics, 2021.

\bibitem{LMMPPS2021} Daniel Lokshtanov, Pranabendu Misra, Joydeep Mukherjee, Geevarghese Philip, Fahad Panolan, Saket Saurabh {\it 2-Approximating Feedback Vertex Set in Tournaments}, ACM Transactions on Algorithms, 2021.

\bibitem{NSS2020} Reza Naserasr, Sagnik Sen and \'{E}ric Sopena. {\it The homomorphism order of signed graphs}, Journal of Combinatorial Mathematics and Combinatorial Computing 2020.


A list of conference publications ordered alphabetically (last updated November 2021):

\bibitem{BFMNR2019} Laurent Beaudou, Florent Foucaud, Florent Madelaine, Lhouari Nourine and Ga\'etan Richard, {\it Complexity of conjunctive regular path query homomorphisms}, Proceedings of the 15th Conference on Computability in Europe CIE 2019.

\bibitem{BFN2020} Laurent Beaudou, Florent Foucaud and Reza Naserasr, {\it Smallest $C_{2l+1}$-critical graphs of odd-girth $2k+1$}, Proceedings of the 6th International Conference on Algorithms and Discrete Applied Mathematics CALDAM 2020.

\bibitem{CDFGLR2020} Dibyayan Chakraborty, Sandip Das, Florent Foucaud, Harmender Gahlawat, Dimitri Lajou and Bodhayan Roy, {\it Algorithms and complexity for geodetic sets on planar and chordal graphs}, Proceedings of the 31st International Symposium on Algorithms and Computation, ISAAC 2020.

\bibitem{CFGGR2020} Dibyayan Chakraborty, Florent Foucaud, Harmender Gahlawat, Subir K. Ghosh and Bodhayan Roy, {\it 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.

\bibitem{CDM2019} Dibyayan Chakraborty, Sandip Das, and Joydeep Mukherjee. {\it Dominating set on overlap graphs of rectangles intersecting a line}, International Computing and Combinatorics Conference, 2019.

\bibitem{DNS2020} Soura S. Das, Soumen Nandi, Sagnik Sen, {\it The relative Oriented Clique Number of Triangle-free Planar Graphs is 10}, CALDAM 2020.

\bibitem{DRS2021} Sandip Das, Siddani B. Rao, and Uma K. Sahoo,

	{\it On degree sequences and eccentricities in pseudoline arrangement graphs}, Proc. CALDAM 2021. 

\bibitem{DFNS2020} Sanjana Dey, Florent Foucaud, Subhas C. Nandy and Arunabha Sen, {\it Discriminating codes in geometric setups}, Proceedings of the 31st International Symposium on Algorithms and Computation ISAAC 2020.

\bibitem{FGPS2020} Florent Foucaud, Benjamin Gras, Anthony Perez and Florian Sikora, {\it On the complexity of broadcast domination and multipacking in digraphs}, Proceeedings of the 31st International Workshop on Combinatorial Algorithms IWOCA 2020.

\bibitem{FHLMP19} Florent Foucaud, Hervé Hocquard, Dimitri Lajou, Valia Mitsou and Th\'eo Pierron, {\it Parameterized complexity of edge-coloured and signed graph homomorphism problems}, Proceedings of the 14th International Symposium on Parameterized and Exact Computation IPEC 2019.

\bibitem{FKKMR2020} Florent Foucaud, Shih-Shun Kao, Ralf Klasing, Mirka Miller and Joe Ryan, {\it Monitoring the edges of a graph using distances. Discrete Applied Mathematics}, to appear in the Special issue for CALDAM 2020.

\bibitem{FMNNV2021} Florent Foucaud, Suchismita Mishra, Narayanan Narayanan, Reza Naserasr and Petru Valicov, {\it Cliques in exact distance powers of graphs of given maximum degree}, Presented at LAGOS 2021, to appear in Procedia Computer Science.

\bibitem{FKMR2020} Florent Foucaud, Ralf Klasing, Mirka Miller and Joe Ryan, {\it Monitoring the edges of a graph using distances}, Proceedings of the 6th International Conference on Algorithms and Discrete Applied Mathematics CALDAM 2020.

\bibitem{LAJOU2020} Dimitri Lajou, {\it On Cartesian products of signed graphs}, CALDAM 2020.

\bibitem{DMS2021} Sandip Das, Joydeep Mukherjee, and Uma K. Sahoo, {\it Outer 1-String Graphs of Girth at Least Five are 3-Colorable}, Extended Abstracts EuroComb 2021.

\bibitem{LNSS2021} Abhiruk Lahiri, Soumen Nandi, Taruni S, Sagnik Sen, {\it On Chromatic number of (n,m)-graphs}, Extended Abstracts EuroComb 2021.

\bibitem{DPDRBS2021} Chirstopher Duffy, Pavan PD, Sandeep RB, Sagnik Sen, {\it On deeply critical oriented cliques}, Extended Abstracts EuroComb 2021.