C.R. Subramanian
Research Interests:
Probabilistic Combinatorics
Graph Theory
Combinatorial Algorithms
Publications :
-
Kunal Dutta and C.R. Subramanian,
On induced acyclic subgraphs in sparse random digraphs
Accepted by European Conference on Combinatorics, Graph
Theory and Applications (EuroComb-2011), Budapest, 2011.
-
N.R. Aravind, N. Narayanan and C.R. Subramanian,
Oriented colouring of some graph products
To appear in Discussiones Mathematicae Graph Theory, 2011.
-
N.R. Aravind, T. Karthick and C.R. Subramanian,
Bounding $\chi$ in terms of $\omega$ and $\Delta$ for
some classes of graphs
Discrete Mathematics, 311 (12) : 911-920, 2011.
-
Kunal Dutta and C.R. Subramanian,
Induced acyclic subgraphs in random digraphs : Improved
bounds
Proceedings of AofA-2010 (21st International
Meeting on Probabilistic, Combinatorial and Asymptotic Methods for the
Analysis of Algorithms), Vienna, Austria, June 2010, pp. 159-174.
-
Kunal Dutta and C.R. Subramanian,
A 2-point concentration of induced acyclic tournaments in random
digraphs,
Proceedings of LATIN-2010 (9th Latin American
Theoretical Informatics Symposium),
Oaxaca, Mexico, April 2010, pp. 627-637.
-
N.R. Aravind and C.R. Subramanian,
Forbidden subgraph colorings and the oriented chromatic number,
Proceedings of IWOCA-2009 (20th International Workshop on
Combinatorial Algorithms), Czech June 2009, pp. 60-71.
-
N.R. Aravind and C.R. Subramanian,
Intersection Dimension and Maximum Degree,
Proceedings of LAGOS-2009 (V Latin-American Algorithms, Graphs
and Optimization Symposium), Brazil, November 3-7, 2009.
-
N.R. Aravind and C.R. Subramanian,
Bounds on edge colorings with restrictions on the union of
color classes,
SIAM Journal on Discrete Mathematics, 24 (3) : 841-852, 2010.
-
N.R. Aravind and C.R. Subramanian,
Bounds on vertex colorings with restrictions on the union of
color classes,
Journal of Graph Theory, 66 : 213-234, 2011.
-
Rahul Muthu, N. Narayanan and C.R. Subramanian,
Optimal acyclic edge coloring of grid like graphs
Discrete Mathematics, 310 (21) : 2769-2775, 2010.
-
N.S. Narayanaswamy and C.R. Subramanian,
Dominating Set Based Exact Algorithms for 3-Coloring,
Information Processing Letters, 111 (6), 251-255, 2011.
-
Sounaka Mishra, Venkatesh Raman, Saket Saurabh, Somnath Sikdar and
C. R. Subramanian,
The Complexity of Konig Vertex Deletion and Other Konig Subgraph
Problems,
To appear in Algorithmica.
-
Rahul Muthu, N. Narayanan and C.R. Subramanian,
On k-Intersection Edge Colourings
Discussiones Mathematicae Graph Theory 29(2) (2009) 411-418.
Also presented in CID-2007 (Colourings, Independence and Domination,
12th Workshop on Graph Theory), September 2007, Poland.
-
C.R. Subramanian,
List hereditary colorings
Extended abstract of the Invited Talk.
To appear in the Proceedings of the ICDM (International Conference
on Discrete Mathematics-2008),
Mysore, India, June 2008. To be published by
Ramanujan Mathematical Society.
-
Joel Spencer and C.R. Subramanian,
On the size of induced acyclic subgraphs in random digraphs,
Discrete Mathematics & Theoretical Computer Science, Vol. 10:2,
2008, pp.47-54.
-
Sounaka Mishra, Venkatesh Raman, Saket Saurabh, Somnath Sikdar and
C. R. Subramanian,
The Complexity of Finding Subgraphs whose Matching Number Equals
the Vertex Cover Number,
Proceedings of ISAAC-2007, December 2007, Sendai, Japan,
Springer LNCS 4835, 268-279.
-
Rahul Muthu, N. Narayanan and C.R. Subramanian,
Improved bounds on acyclic edge coloring
Discrete Mathematics, 307:23, 2007, 3063-3069.
A preliminary version appeared in the Proceedings of GRACO-05.
-
Rahul Muthu, N. Narayanan and C.R. Subramanian,
Acyclic edge colouring of outerplanar graphs,
Proceedings of AAIM-2007, June 2007.
-
C.R. Subramanian,
List set coloring : bounds and algorithms,
Combinatorics, Probability and Computing 16 (2007),
145-158.
-
C.R. Subramanian,
Analysis of a heuristic for acyclic edge colouring,
Information Processing Letters, 99 (2006), 227-229.
-
Rahul Muthu, N. Narayanan and C.R. Subramanian,
Optimal acyclic edge colouring of grid like graphs,
Proceedings of COCOON-2006, LNCS 4112, 360-367.
-
Venkatesh Raman, Saket Saurabh and C.R. Subramanian,
Faster fixed parameter tractable algorithms for finding
feedback vertex sets,
ACM Transactions on Algorithms. Vol. 2, No. 3, July 2006,
403-415.
-
R. Balasubramanian and C.R. Subramanian,
On Sampling Colorings of Bipartite Graphs,
Discrete Mathematics and Theoretical Computer Science, 8 (2006),
17-30
-
Venkatesh Raman, Saket Saurabh and C.R. Subramanian,
Faster algorithms for feedback vertex set,
Electronic Notes in Discrete Mathematics, 19 (2005), 273-279,
Proceedings of GRACO-2005.
-
Rahul Muthu, N. Narayanan and C.R. Subramanian,
Improved bounds on acyclic edge coloring,
Electronic Notes in Discrete Mathematics, 19 (2005), 171-177,
Proceedings of GRACO-2005.
-
L.S. Chandran, Vadim V. Lozin and C.R. Subramanian,
Graphs of low chordality,
Discrete Mathematics and Theoretical Computer Science, 7 (2005),
25-36
-
L. Sunil Chandran and C.R. Subramanian,
Girth and treewidth,
Journal of Combinatorial Theory, Series B, 93 (2005), 23-32
-
C.R. Subramanian,
Finding Induced Acyclic Subgraphs in Random Digraphs,
The Electronic Journal of Combinatorics 10 (2003), #R46
-
L. Sunil Chandran and C.R. Subramanian,
A spectral lower bound for the treewidth of a graph and
its consequences,
Information Processing Letters,
Volume 87, Issue 4, 31 August 2003, pages 195-200.
-
L. Sunil Chandran, T. Kavitha and C.R. Subramanian,
Isoperimetric inequalities and the width parameters of graphs,
Proceedings of the Ninth International Conference on Computing
and Combinatorics (COCOON)-2003,
Big Sky, MT, USA, July 2003,
Springer-Verlag LNCS.
-
V. Raman, S. Saurabh and C.R. Subramanian,
Faster Fixed Parameter Tractable Algorithms for Undirected Feedback
Vertex Set Problem,
Proceedings of the 13th International Symposium on
Algorithms and Computation (ISAAC) - 2002,
Vancouver, BC, Canada, Nov. 2002, Springer-Verlag LNCS 2518,
page 241-252.
-
C.R. Subramanian and C.E. Veni Madhavan,
General Partitioning on Random Graphs,
Journal of Algorithms,
42, 153-172 (2002).
-
C.R. Subramanian,
Paths of specified length in a random $k$-partite graph,
Discrete Mathematics \& Theoretical
Computer Science,
Vol. 4, No.2 (2001), pp. 133-138,
http://dmtcs.loria.fr.
-
C.R. Subramanian,
Coloring Sparse Random Graphs in Polynomial Average Time,
Proceedings of the
8th Annual European Symposium on Algorithms (ESA'00),
Saarbr\"ucken, 2000, Springer-Verlag LNCS 1879, 415-426.
-
C.R. Subramanian,
Algorithms for Coloring Random $k$-colorable Graphs,
Combinatorics, Probability and Computing,
9 (2000), 45-77.
-
C.R. Subramanian,
Minimum Coloring $k$-colorable Graphs in polynomial Average
Time,
Journal of Algorithms,
33, 112-123 (1999).
-
C.P. Schnorr and C.R. Subramanian,
Almost optimal (on the average) algorithms
for boolean matrix product witnesses, computing diameter,
Proceedings of RANDOM'98 International Workshop,
Barcelona, 1998, Springer-Verlag LNCS 1518, 218-231.
-
C.R. Subramanian, M. Furer and C.E. Veni Madhavan,
Algorithms for Coloring Semi-Random Graphs,
Random Structures and Algorithms,
13, 125-158 (1998).
-
K. Sridharan, C.R. Subramanian and N. Sudha,
Some Properties of Touching Distances for Polygons and
Polyhedra,
Applied Mathematics Letters,
Vol. 11, No. 5, pp. 1-7, 1998.
-
C.R. Subramanian and C.E. Veni Madhavan,
Existence of Homeomorphic Subgraphs in Chordal Graphs,
Applied Mathematics Letters,
Volume {\bf 10}, No. 3, 1997, pp. 17-22.
-
C.R. Subramanian,
Minimum Coloring Random and Semi-Random Graphs in Polynomial
Expected Time,
Proceedings of the 36th Annual IEEE
Symposium on Foundations of Computer Science (FOCS'95),
Milwaukee, USA, 1995, 463-472.
Preprints :
-
Kunal Dutta, Dhruv Mubayi and C.R. Subramanian,
New lower bounds for the independence number of sparse graphs
and hypergraphs
manuscript, February 2011.
-
T. Karthick and C.R. Subramanian,
On star coloring of graphs
manuscript, October 2010.
-
C.R. Subramanian,
Improved FPT algorithms for graph isomorphism,
manuscript in preparation, July 2010.
-
N.R. Aravind and C.R. Subramanian,
A refinement of the Local Lemma and bounds on forbidden
subgraph chromatic numbers,
manuscript in preparation.
-
Rahul Muthu, N. Narayanan and C.R. Subramanian,
Acyclic edge colouring of partial 2-trees,
manuscript, 2007.
-
Rahul Muthu and C.R. Subramanian,
Cartesian product and acyclic edge colouring,
manuscript, 2007.
-
Rahul Muthu, N. Narayanan and C.R. Subramanian,
Some graph classes satisfying acyclic edge colouring conjecture,
manuscript. 2010.
-
C.R. Subramanian,
Coloring graphs using random lists,
manuscript.
-
C.R. Subramanian,
List hereditary colorings of graphs and hypergraphs,
manuscript in preparation.
-
Kunal Dutta and C.R. Subramanian,
A 2-point concentration of induced acyclic tournaments in random
digraphs,
manuscript.
-
Kunal Dutta and C.R. Subramanian,
Improved concentration results on induced acyclic subgraphs in
random digraphs,
manuscript in preparation.
-
C.R. Subramanian,
Vertex Covers : Parameterizing Above the Requirement,
manuscript, February 2001.