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 (EuroComb2011), 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) : 911920, 2011.

Kunal Dutta and C.R. Subramanian,
Induced acyclic subgraphs in random digraphs : Improved
bounds
Proceedings of AofA2010 (21st International
Meeting on Probabilistic, Combinatorial and Asymptotic Methods for the
Analysis of Algorithms), Vienna, Austria, June 2010, pp. 159174.

Kunal Dutta and C.R. Subramanian,
A 2point concentration of induced acyclic tournaments in random
digraphs,
Proceedings of LATIN2010 (9th Latin American
Theoretical Informatics Symposium),
Oaxaca, Mexico, April 2010, pp. 627637.

N.R. Aravind and C.R. Subramanian,
Forbidden subgraph colorings and the oriented chromatic number,
Proceedings of IWOCA2009 (20th International Workshop on
Combinatorial Algorithms), Czech June 2009, pp. 6071.

N.R. Aravind and C.R. Subramanian,
Intersection Dimension and Maximum Degree,
Proceedings of LAGOS2009 (V LatinAmerican Algorithms, Graphs
and Optimization Symposium), Brazil, November 37, 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) : 841852, 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 : 213234, 2011.

Rahul Muthu, N. Narayanan and C.R. Subramanian,
Optimal acyclic edge coloring of grid like graphs
Discrete Mathematics, 310 (21) : 27692775, 2010.

N.S. Narayanaswamy and C.R. Subramanian,
Dominating Set Based Exact Algorithms for 3Coloring,
Information Processing Letters, 111 (6), 251255, 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 kIntersection Edge Colourings
Discussiones Mathematicae Graph Theory 29(2) (2009) 411418.
Also presented in CID2007 (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 Mathematics2008),
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.4754.

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 ISAAC2007, December 2007, Sendai, Japan,
Springer LNCS 4835, 268279.

Rahul Muthu, N. Narayanan and C.R. Subramanian,
Improved bounds on acyclic edge coloring
Discrete Mathematics, 307:23, 2007, 30633069.
A preliminary version appeared in the Proceedings of GRACO05.

Rahul Muthu, N. Narayanan and C.R. Subramanian,
Acyclic edge colouring of outerplanar graphs,
Proceedings of AAIM2007, June 2007.

C.R. Subramanian,
List set coloring : bounds and algorithms,
Combinatorics, Probability and Computing 16 (2007),
145158.

C.R. Subramanian,
Analysis of a heuristic for acyclic edge colouring,
Information Processing Letters, 99 (2006), 227229.

Rahul Muthu, N. Narayanan and C.R. Subramanian,
Optimal acyclic edge colouring of grid like graphs,
Proceedings of COCOON2006, LNCS 4112, 360367.

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,
403415.

R. Balasubramanian and C.R. Subramanian,
On Sampling Colorings of Bipartite Graphs,
Discrete Mathematics and Theoretical Computer Science, 8 (2006),
1730

Venkatesh Raman, Saket Saurabh and C.R. Subramanian,
Faster algorithms for feedback vertex set,
Electronic Notes in Discrete Mathematics, 19 (2005), 273279,
Proceedings of GRACO2005.

Rahul Muthu, N. Narayanan and C.R. Subramanian,
Improved bounds on acyclic edge coloring,
Electronic Notes in Discrete Mathematics, 19 (2005), 171177,
Proceedings of GRACO2005.

L.S. Chandran, Vadim V. Lozin and C.R. Subramanian,
Graphs of low chordality,
Discrete Mathematics and Theoretical Computer Science, 7 (2005),
2536

L. Sunil Chandran and C.R. Subramanian,
Girth and treewidth,
Journal of Combinatorial Theory, Series B, 93 (2005), 2332

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 195200.

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,
SpringerVerlag 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, SpringerVerlag LNCS 2518,
page 241252.

C.R. Subramanian and C.E. Veni Madhavan,
General Partitioning on Random Graphs,
Journal of Algorithms,
42, 153172 (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. 133138,
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, SpringerVerlag LNCS 1879, 415426.

C.R. Subramanian,
Algorithms for Coloring Random $k$colorable Graphs,
Combinatorics, Probability and Computing,
9 (2000), 4577.

C.R. Subramanian,
Minimum Coloring $k$colorable Graphs in polynomial Average
Time,
Journal of Algorithms,
33, 112123 (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, SpringerVerlag LNCS 1518, 218231.

C.R. Subramanian, M. Furer and C.E. Veni Madhavan,
Algorithms for Coloring SemiRandom Graphs,
Random Structures and Algorithms,
13, 125158 (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. 17, 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. 1722.

C.R. Subramanian,
Minimum Coloring Random and SemiRandom Graphs in Polynomial
Expected Time,
Proceedings of the 36th Annual IEEE
Symposium on Foundations of Computer Science (FOCS'95),
Milwaukee, USA, 1995, 463472.
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 2trees,
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 2point 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.