2025
Variants of the Gyárfás-Sumner conjecture: Oriented trees and rainbow paths.
J. Graph Theory, January, 2025
List recoloring of planar graphs.
Discret. Appl. Math., 2025
2024
New bounds on the anti-Ramsey numbers of star graphs via maximum edge <i>q</i>-coloring.
Discret. Math., April, 2024
s-Club Cluster Vertex Deletion on interval and well-partitioned chordal graphs.
Discret. Appl. Math., March, 2024
Weakening Total Coloring Conjecture: Weak TCC and Hadwiger's Conjecture on Total Graphs.
Electron. J. Comb., 2024
Krenn-Gu Conjecture for Sparse Graphs.
Proceedings of the 49th International Symposium on Mathematical Foundations of Computer Science, 2024
Total Domination, Separated-Cluster, CD-Coloring: Algorithms and Hardness.
Proceedings of the LATIN 2024: Theoretical Informatics, 2024
Two Results on LPT: A Near-Linear Time Algorithm and Parcel Delivery Using Drones.
Proceedings of the 44th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2024
2023
Template-driven rainbow coloring of proper interval graphs.
Discret. Appl. Math., March, 2023
χ-binding functions for squares of bipartite graphs and its subclasses.
CoRR, 2023
Total Domination, Separated Clusters, CD-Coloring: Algorithms and Hardness.
CoRR, 2023
Graph-theoretic insights on the constructability of complex entangled states.
CoRR, 2023
2022
Upper bounding rainbow connection number by forest number.
Discret. Math., 2022
Improved approximation for maximum edge colouring problem.
Discret. Appl. Math., 2022
On graphs whose eternal vertex cover number and vertex cover number coincide.
Discret. Appl. Math., 2022
Towards a conjecture on the recoloring diameter of planar graphs.
CoRR, 2022
Perfect Matchings and Quantum Physics: Progress on Krenn's Conjecture.
CoRR, 2022
2021
Algorithms and Complexity of s-Club Cluster Vertex Deletion.
Proceedings of the Combinatorial Algorithms - 32nd International Workshop, 2021
2020
Combinatorial Lower Bounds for 3-Query LDCs.
Proceedings of the 11th Innovations in Theoretical Computer Science Conference, 2020
List Distinguishing Number of p<sup> th</sup> Power of Hypercube and Cartesian Powers of a Graph.
Proceedings of the Algorithms and Discrete Applied Mathematics, 2020
2019
Hadwiger's conjecture for squares of 2-trees.
Eur. J. Comb., 2019
On induced colourful paths in triangle-free graphs.
Discret. Appl. Math., 2019
On Graphs with Minimal Eternal Vertex Cover Number.
Proceedings of the Algorithms and Discrete Applied Mathematics, 2019
2018
On Eulerian orientations of even-degree hypercubes.
Oper. Res. Lett., 2018
Sublinear approximation algorithms for boxicity and related problems.
Discret. Appl. Math., 2018
Approximation bounds on maximum edge 2-coloring of dense graphs.
CoRR, 2018
Spanning Tree Congestion and Computation of Generalized Győri-Lov{á}sz Partition.
CoRR, 2018
Algorithms and Bounds for Very Strong Rainbow Coloring.
Proceedings of the LATIN 2018: Theoretical Informatics, 2018
Spanning Tree Congestion and Computation of Generalized Györi-Lovász Partition.
Proceedings of the 45th International Colloquium on Automata, Languages, and Programming, 2018
2017
Rainbow colouring of split graphs.
Discret. Appl. Math., 2017
2016
Upper bound on cubicity in terms of boxicity for graphs of low chromatic number.
Discret. Math., 2016
An Approach to Hadwiger's Conjecture through Squares of Chordal Graphs.
CoRR, 2016
Separation Dimension of Graphs and Hypergraphs.
Algorithmica, 2016
On the Parameterized Complexity of Biclique Cover and Partition.
Proceedings of the 11th International Symposium on Parameterized and Exact Computation, 2016
Hadwiger's Conjecture and Squares of Chordal Graphs.
Proceedings of the Computing and Combinatorics - 22nd International Conference, 2016
2015
Separation Dimension of Bounded Degree Graphs.
SIAM J. Discret. Math., 2015
Boxicity and cubicity of product graphs.
Eur. J. Comb., 2015
Heterochromatic paths in edge colored graphs without small cycles and heterochromatic-triangle-free graphs.
Eur. J. Comb., 2015
Rainbow matchings in strongly edge-colored graphs.
Discret. Math., 2015
2014
2-Connecting outerplanar graphs without blowing up the pathwidth.
Theor. Comput. Sci., 2014
Representing a Cubic Graph as the Intersection Graph of Axis-Parallel Boxes in Three Dimensions.
SIAM J. Discret. Math., 2014
Rainbow Connection Number of Graph Power and Graph Products.
Graphs Comb., 2014
Rainbow Connection Number and Radius.
Graphs Comb., 2014
Cubicity, degeneracy, and crossing number.
Eur. J. Comb., 2014
On Additive Combinatorics of Permutations of ℤ<sub>n</sub>.
Discret. Math. Theor. Comput. Sci., 2014
A constant factor approximation algorithm for boxicity of circular arc graphs.
Discret. Appl. Math., 2014
Separation dimension of sparse graphs.
CoRR, 2014
Approximating the Cubicity of Trees.
CoRR, 2014
Lower bounds for boxicity.
Comb., 2014
Boxicity and Separation Dimension.
Proceedings of the Graph-Theoretic Concepts in Computer Science, 2014
2013
On the SIG-Dimension of Trees Under the L ∞-Metric.
Graphs Comb., 2013
Bipartite Powers of k-chordal Graphs.
Discret. Math. Theor. Comput. Sci., 2013
Product Dimension of Forests and Bounded Treewidth Graphs.
Electron. J. Comb., 2013
Inapproximability of Rainbow Colouring.
Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2013
2012
Rainbow connection number and connected dominating sets.
J. Graph Theory, 2012
Acyclic Edge Coloring of Triangle-Free Planar Graphs.
J. Graph Theory, 2012
Acyclic edge coloring of 2-degenerate graphs.
J. Graph Theory, 2012
Maximum weight independent sets in hole- and dart-free graphs.
Discret. Appl. Math., 2012
Parameterized and Approximation Algorithms for Boxicity
CoRR, 2012
Rainbow Connection Number and Connectivity.
Electron. J. Comb., 2012
Polynomial Time and Parameterized Approximation Algorithms for Boxicity.
Proceedings of the Parameterized and Exact Computation - 7th International Symposium, 2012
Rainbow Colouring of Split and Threshold Graphs.
Proceedings of the Computing and Combinatorics - 18th Annual International Conference, 2012
2011
Acyclic Edge-Coloring of Planar Graphs.
SIAM J. Discret. Math., 2011
Boxicity and Poset Dimension.
SIAM J. Discret. Math., 2011
Chordal Bipartite Graphs with High Boxicity.
Graphs Comb., 2011
Boxicity of Circular Arc Graphs.
Graphs Comb., 2011
2010
<i>d</i>-Regular graphs of acyclic chromatic index at least <i>d</i>+2.
J. Graph Theory, 2010
Cubicity of interval graphs and the claw number.
J. Graph Theory, 2010
Boxicity and cubicity of asteroidal triple free graphs.
Discret. Math., 2010
The hardness of approximating the boxicity, cubicity and threshold dimension of a graph.
Discret. Appl. Math., 2010
Geometric Representation of Graphs in Low Dimension Using Axis Parallel Boxes.
Algorithmica, 2010
2009
Acyclic edge coloring of graphs with maximum degree 4.
J. Graph Theory, 2009
On the cubicity of bipartite graphs.
Inf. Process. Lett., 2009
On the Structure of Contractible Edges in <i>k</i>-connected Partial <i>k</i>-trees.
Graphs Comb., 2009
Hadwiger's conjecture for proper circular arc graphs.
Eur. J. Comb., 2009
An upper bound for Cubicity in terms of Boxicity.
Discret. Math., 2009
Boxicity of Halin graphs.
Discret. Math., 2009
Cubicity, boxicity, and vertex cover.
Discret. Math., 2009
Bounds on isoperimetric values of trees.
Discret. Math., 2009
A note on acyclic edge coloring of complete bipartite graphs.
Discret. Math., 2009
Acyclic Edge coloring of Planar Graphs
CoRR, 2009
On the SIG dimension of trees under $L_{\infty}$ metric.
CoRR, 2009
On the Arrangement of Cliques in Chordal Graphs with respect to the Cuts.
Ars Comb., 2009
On the Cubicity of AT-Free Graphs and Circular-Arc Graphs.
Proceedings of the Graph Theory, 2009
2008
Boxicity and maximum degree.
J. Comb. Theory B, 2008
Hadwiger Number and the Cartesian Product of Graphs.
Graphs Comb., 2008
The cubicity of hypercube graphs.
Discret. Math., 2008
Acyclic edge coloring of subcubic graphs.
Discret. Math., 2008
Isoperimetric Problem and Meta-Fibonacci Sequences.
Proceedings of the Computing and Combinatorics, 14th Annual International Conference, 2008
Finding a Box Representation for a Graph in O(n<sup>2</sup>Δ<sup>2</sup>lnn) Time.
Proceedings of the 2008 International Conference on Information Technology, 2008
2007
On the relationship between ATSP and the cycle cover problem.
Theor. Comput. Sci., 2007
The stable set problem and the thinness of a graph.
Oper. Res. Lett., 2007
A note on the Hadwiger number of circular arc graphs.
Inf. Process. Lett., 2007
On the Cubicity of Interval Graphs.
Electron. Notes Discret. Math., 2007
On the Hadwiger's conjecture for graph products.
Discret. Math., 2007
A Combinatorial Family of Near Regular LDPC Codes.
Proceedings of the IEEE International Symposium on Information Theory, 2007
2006
The carvingwidth of hypercubes.
Discret. Math., 2006
The treewidth and pathwidth of hypercubes.
Discret. Math., 2006
A linear time algorithm to list the minimal separators of chordal graphs.
Discret. Math., 2006
Boxicity of series-parallel graphs.
Discret. Math., 2006
Representing graphs as the intersection of axis-parallel cubes
CoRR, 2006
Geometric representation of graphs in low dimension
CoRR, 2006
Hardness of Approximation Results for the Problem of Finding the Stopping Distance in Tanner Graphs.
Proceedings of the FSTTCS 2006: Foundations of Software Technology and Theoretical Computer Science, 2006
Geometric Representation of Graphs in Low Dimension.
Proceedings of the Computing and Combinatorics, 12th Annual International Conference, 2006
2005
On the cubicity of certain graphs.
Inf. Process. Lett., 2005
Refined memorization for vertex cover.
Inf. Process. Lett., 2005
On the Hadwiger number of hypercubes and its generalizations.
Electron. Notes Discret. Math., 2005
Graphs of low chordality.
Discret. Math. Theor. Comput. Sci., 2005
2004
On the Number of Minimum Cuts in a Graph.
SIAM J. Discret. Math., 2004
Minimum cuts, girth and a spectral threshold.
Inf. Process. Lett., 2004
Refined Memorisation for Vertex Cover.
Proceedings of the Parameterized and Exact Computation, First International Workshop, 2004
2003
Generating and characterizing the perfect elimination orderings of a chordal graph.
Theor. Comput. Sci., 2003
A High Girth Graph Construction.
SIAM J. Discret. Math., 2003
A spectral lower bound for the treewidth of a graph and its consequences.
Inf. Process. Lett., 2003
A lower bound for the hitting set size for combinatorial rectangles and an application.
Inf. Process. Lett., 2003
Isoperimetric Inequalities and the Width Parameters of Graphs.
Proceedings of the Computing and Combinatorics, 9th Annual International Conference, 2003
2002
Approximations for ATSP with Parametrized Triangle Inequality.
Proceedings of the STACS 2002, 19th Annual Symposium on Theoretical Aspects of Computer Science, Antibes, 2002
2001
Edge Connectivity vs Vertex Connectivity in Chordal Graphs.
Proceedings of the Computing and Combinatorics, 7th Annual International Conference, 2001
A Linear Time Algorithm for Enumerating All the Minimum and Minimal Separators of a Chordal Graph.
Proceedings of the Computing and Combinatorics, 7th Annual International Conference, 2001
1999
A High Girth Graph Construction and a Lower Bound for Hitting Set Size for Combinatorial Rectangles.
Proceedings of the Foundations of Software Technology and Theoretical Computer Science, 1999
