Mathew C. Francis
Associate Professor
Computer Science Unit
Indian Statistical Institute, Chennai Centre
| email: |
Research Interests: Algorithmic Graph Theory, Geometric Intersection Graphs.
Ph.D. Thesis - “Intersection graphs of boxes and cubes” (pdf)
Publications
In journals:
Boxicity and Maximum Degree, with L. Sunil Chandran and Naveen Sivadasan, Journal of Combinatorial Theory, Series B, 98(2):443–445, 2008.
On the Cubicity of Interval Graphs, with L. Sunil Chandran and Naveen Sivadasan, Graphs and Combinatorics, 25(2):169–179, 2009.
Boxicity of Halin Graphs, with L. Sunil Chandran and Santhosh Suresh, Discrete Mathematics, 309(10):3233–3237, 2009.
Geometric Representation of Graphs in Low Dimension Using Axis Parallel Boxes, with L. Sunil Chandran and Naveen Sivadasan, Algorithmica, 56(2):129–140, 2010.
Non-contractible Non-edges in 2-connected Graphs, with Anita Das, Rogers Mathew and N. Sadagopan, Information Processing Letters, 110(23), 1044–1048, 2010.
Boxicity of Leaf Powers, with L. Sunil Chandran and Rogers Mathew, Graphs and Combinatorics, 27(1):61–72, 2011.
Chordal Bipartite Graphs with High Boxicity, with L. Sunil Chandran and Rogers Mathew, Graphs and Combinatorics, 27(3):353–362, 2011.
Cubicity and Bandwidth, with L. Sunil Chandran and Naveen Sivadasan, Graphs and Combinatorics, 29(1):45–69, 2013.
Segment Representation of a Subclass of Co-planar Graphs, with Jan Kratochvíl and Tomáš Vyskočil, Discrete Mathematics, 312(10):1815–1818, 2012.
Recognition and Characterization of Chronological Interval Digraphs, with Sandeep Das, Pavol Hell and Jing Huang, The Electronic Journal of Combinatorics, 20(3) (2013) #P5.
The Maximum Clique Problem in Multiple Interval Graphs, with Daniel Gonçalves and Pascal Ochem, Algorithmica, 71(4):812–836, 2015.
Blocking Quadruple: A New Obstruction to Circular-Arc Graphs, with Pavol Hell and Juraj Stacho, SIAM Journal on Discrete Mathematics, 28(2):631–655, 2014.
Strong Chromatic Index of Chordless Graphs, with Manu Basavaraju, Journal of Graph Theory, 80(1):58–68, 2015.
Partially Polynomial Kernels for Set Cover and Test Cover, with Manu Basavaraju, M. S. Ramanujan and Saket Saurabh, SIAM Journal on Discrete Mathematics, 30(3):1401–1423, 2016.
VPG and EPG Bend-numbers of Halin Graphs, with Abhiruk Lahiri, Discrete Applied Mathematics, 215:95–105, 2016.
Uniquely Restricted Matchings in Interval Graphs, with Dalu Jacob and Satyabrata Jana, SIAM Journal on Discrete Mathematics, 32(1):148–172, 2018.
On Induced Colourful Paths in Triangle-Free Graphs, with Jasine Babu, Manu Basavaraju and L. Sunil Chandran, Discrete Applied Mathematics, 255:109–116, 2019.
On the Stab Number of Rectangle Intersection Graphs, with Dibyayan Chakraborty, Theory of Computing Systems, 64:681–734, 2020.
On Rectangle Intersection Graphs with Stab Number at most Two, with Dibyayan Chakraborty, Sandip Das and Sagnik Sen, Discrete Applied Mathematics, 289:354–365, 2021.
Representing Graphs as the Intersection of Cographs and Threshold Graphs, with Daphna Chacko, The Electronic Journal of Combinatorics, 28(3):P3.11, 2021.
Recognizing k-Clique Extendible Orderings, with Rian Neogi and Venkatesh Raman, Algorithmica, 83, 3338–3362, 2021.
Extending Some Results on the Second Neighborhood Conjecture, with Suresh Dara, Dalu Jacob and N. Narayanan, Discrete Applied Mathematics, 311, 1–17, 2022.
On Graphs whose Eternal Vertex Cover Number and Vertex Cover Number Coincide, with Jasine Babu, L. Sunil Chandran, Veena Prabhakaran, Deepak Rajendraprasad and Nandini J. Warrier, Discrete Applied Mathematics, 319:171–182, 2022.
On Subclasses of Interval Count Two and on Fishburn's Conjecture, with Lívia S. Medeiros, Fabiano S. Oliveira and Jayme L. Szwarcfiter, Discrete Applied Mathematics, 323:236–251, 2022.
On the Kernel and Related Problems in Interval Digraphs, with Pavol Hell and Dalu Jacob, Algorithmica, 85:1522–1559, 2023.
The Lexicographic Method for the Threshold Cover Problem, with Dalu Jacob, Discrete Mathematics, 346(6):113364, 2023.
A p-centered Coloring for the Grid Using O(p) Colors, with Drimit Pattanayak, Discrete Mathematics, 347(1):113670, 2024.
Weakening Total Coloring Conjecture: Weak TCC and Hadwiger's Conjecture on Total Graphs, with Manu Basavaraju, L. Sunil Chandran and Ankur Naskar, Electronic Journal of Combinatorics, accepted pending minor revision.
Variants of the Gyárfás-Sumner Conjecture: Oriented Trees and Rainbow Paths, with Manu Basavaraju, L. Sunil Chandran and Karthik Murali, Journal of Graph Theory, accepted pending minor revision.
In conferences:
On the Cubicity of Interval Graphs, with L. Sunil Chandran and Naveen Sivadasan, EuroComb'07, September 2007, Seville, Spain.
Representing Graphs as the Intersection of Axis Parallel Cubes, with L. Sunil Chandran and Naveen Sivadasan, MCDES 2008, May 2008, Bangalore.
On the Cubicity of AT-Free Graphs and Circular-Arc Graphs, with L. Sunil Chandran and Naveen Sivadasan, Graph Theory, Computational Intelligence and Thought, September 2008, Israel.
Chordal Bipartite Graphs with High Boxicity, with L. Sunil Chandran and Rogers Mathew, JCCGG 2009, November 2009, Kanazawa, Japan.
Contact Representations of Planar Graphs with Cubes, with Stefan Felsner, SoCG 2011, June 2011, Paris.
The Maximum Clique Problem in Multiple Interval Graphs, with Daniel Gonçalves and Pascal Ochem, WG 2012, June 2012, Jerusalem.
Obstructions to Chordal Circular-Arc Graphs, with Pavol Hell and Juraj Stacho, LAGOS 2013, April 2013, Playa del Carmen, Mexico.
Partially Polynomial Kernels for Set Cover and Test Cover, with Manu Basavaraju, M. S. Ramanujan and Saket Saurabh, FSTTCS 2013, December 2013, Guwahati, India.
Forbidden Structure Characterization of Circular-Arc Graphs and a Certifying Recognition Algorithm, with Pavol Hell and Juraj Stacho, SODA 2015, January 2015, San Diego.
On Induced Colourful Paths in Triangle-Free Graphs, with Jasine Babu, Manu Basavaraju and L. Sunil Chandran, EuroComb 2017, August 2017, Vienna, Austria.
Dushnik-Miller Dimension of Contact Systems of d-dimensional Boxes, with Daniel Gonçalves, EuroComb 2017, August 2017, Vienna, Austria.
On Rectangle Intersection Graphs with Stab Number at most Two, with Dibyayan Chakraborty, Sandip Das and Sagnik Sen, CALDAM 2019, February 2019, Kharagpur, India.
On Graphs with Minimal Eternal Vertex Cover Number, with Jasine Babu, L. Sunil Chandran, Veena Prabhakaran, Deepak Rajendraprasad and J. Nandini Warrier, CALDAM 2019, February 2019, Kharagpur, India.
The Lexicographic Method for the Threshold Cover Problem, with Dalu Jacob, CALDAM 2020, February 2020, Hyderabad, India.
Recognizing k-clique Extendible Orderings, with Rian Neogi and Venkatesh Raman, WG 2020, June 2020, University of Leeds, UK.
The Linear Arboricity Conjecture for 3-degenerate Graphs, with Manu Basavaraju, Arijit Bishnu and Drimit Pattanayak, WG 2020, June 2020, University of Leeds, UK.
On the Kernel and Related Problems in Interval Digraphs, with Pavol Hell and Dalu Jacob, ISAAC 2021, December 2021, Fukuoka, Japan.
Bounding Threshold Dimension: Realizing Graphic Boolean Functions as the AND of Majority Gates, with Atrayee Majumder and Rogers Mathew, WG 2022, June 2022, Tübingen, Germany.