BZPEERSource author record
Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.
Catalog footprint
Published work
Given a triangle-free graph G with chromatic number k and a proper vertex coloring ϕ of G, it is conjectured that G contains an induced rainbow path on k vertices under ϕ. Scott and Seymour proved the existence of an induced rainbow path on (logloglogk)31−o(1) vertices. We improve this to (logk)21−o(1) vertices. Further, we prove the existence of an induced path that sees 2k colors.
The anti-Ramsey number ar(G,H) with input graph G and pattern graph H, is the maximum positive integer k such that there exists an edge coloring of G using k colors, in which there are no rainbow subgraphs isomorphic to H in G. (H is rainbow if all its edges get distinct colors). The concept of anti-Ramsey number was introduced by Erdös, Simanovitz, and Sós in 1973. Thereafter several researchers investigated this concept in the combinatorial setting. Recently, Feng et al. revisited the anti-Ramsey problem for the pattern graph K1,t (for t≥3) purely from an algorithmic point of view due to its applications in interference modeling of wireless networks. They posed it as an optimization problem, the maximum edge q-coloring problem. For a graph G and an integer q≥2, an edge q-coloring of G is an assignment of colors to edges of G, such that edges incident on a vertex span at most q distinct colors. The maximum edge q-coloring problem seeks to maximize the number of colors in an edge q-coloring of the graph G. Note that the optimum value of the edge q-coloring problem of G equals ar(G,K1,q+1). In this paper, we study ar(G,K1,t), the anti-Ramsey number of stars, for each fixed integer t≥3, both from combinatorial and algorithmic point of view. The first of our main results presents an upper bound for ar(G,K1,q+1), in terms of number of vertices and the minimum degree of G. The second one improves this result for the case of triangle-free input graphs. For a positive integer t, let Ht denote a subgraph of G with maximum number of possible edges and maximum degree t. Our third main result presents an upper bound for ar(G,K1,q+1) in terms of ∣E(Hq−1)∣. All our results have algorithmic consequences.
The \emph{local boxicity} of a graph G, denoted by lbox(G), is the minimum positive integer l such that G can be obtained using the intersection of k (, where k≥l,) interval graphs where each vertex of G appears as a non-universal vertex in at most l of these interval graphs. Let G be a graph on n vertices having m edges. Let Δ denote the maximum degree of a vertex in G. We show that, (i) lbox(G)≤213log∗ΔΔ. There exist graphs of maximum degree Δ having a local boxicity of Ω(logΔΔ). (ii) lbox(G)∈O(lognn). There exist graphs on n vertices having a local boxicity of Ω(lognn). (iii) lbox(G)≤(213log∗m+2)m. There exist graphs with m edges having a local boxicity of Ω(logmm). (iv) the local boxicity of G is at most its \emph{product dimension}. This connection helps us in showing that the local boxicity of the \emph{Kneser graph} K(n,k) is at most 2kloglogn. The above results can be extended to the \emph{local dimension} of a partially ordered set due to the known connection between local boxicity and local dimension. Finally, we show that the \emph{cubicity} of a graph on n vertices of girth greater than g+1 is O(n⌊g/2⌋1logn).
In this note, we give a simple, counting based proof of Fisher's Inequality that does not use any tools from linear algebra.
Given a graph, the conflict-free coloring problem on open neighborhoods (CFON) asks to color the vertices of the graph so that all the vertices have a uniquely colored vertex in its open neighborhood. The smallest number of colors required for such a coloring is called the conflict-free chromatic number and denoted χON(G). In this note, we study this problem on Sk-free graphs where Sk is a star on k+1 vertices. When G is Sk-free, we show that χON(G)=O(k⋅log2+εΔ), for any ε>0, where Δ denotes the maximum degree of G. Further, we show existence of claw-free (S3-free) graphs that require Ω(logΔ) colors.
The closed neighborhood conflict-free chromatic number of a graph G, denoted by χCN(G), is the minimum number of colors required to color the vertices of G such that for every vertex, there is a color that appears exactly once in its closed neighborhood. Pach and Tardos [Combin. Probab. Comput. 2009] showed that χCN(G)=O(log2+εΔ), for any ε>0, where Δ is the maximum degree. In [Combin. Probab. Comput. 2014], Glebov, Szabó and Tardos showed existence of graphs G with χCN(G)=Ω(log2Δ). In this paper, we bridge the gap between the two bounds by showing that χCN(G)=O(log2Δ).
A collection of linear orders on X, say L, is said to \emph{realize} a partially ordered set (or poset) P=(X,⪯) if, for any two distinct x,y∈X, x⪯y if and only if x≺Ly, ∀L∈L. We call L a \emph{realizer} of P. The \emph{dimension} of P, denoted by dim(P), is the minimum cardinality of a realizer of P. A \emph{containment model} MP of a poset P=(X,⪯) maps every x∈X to a set Mx such that, for every distinct x,y∈X, x⪯y if and only if MxMy. We shall be using the collection (Mx)x∈X to identify the containment model MP. A poset P=(X,⪯) is a Containment order of Paths in a Tree (CPT poset), if it admits a containment model MP=(Px)x∈X where every Px is a path of a tree T, which is called the host tree of the model. We show that if a poset P admits a CPT model in a host tree T of maximum degree Δ and radius r, then \rogers{dim(P)≤lglgΔ+(21+o(1))lglglgΔ+lgr+21lglgr+21lgπ+3. This bound is asymptotically tight up to an additive factor of min(21lglglgΔ,21lglgr). Further, let P(1,2;n) be the poset consisting of all the 1-element and 2-element subsets of [n] under `containment' relation and let dim(1,2;n) denote its dimension. The proof of our main theorem gives a simple algorithm to construct a realizer for P(1,2;n) whose cardinality is only an additive factor of at most 23 away from the optimum.
In the first part of this paper, we prove a theorem which is the q-analogue of a generalized modular Ray-Chaudhuri-Wilson Theorem shown in [Alon, Babai, Suzuki, J. Combin. Theory Series A, 1991]. It is also a generalization of the main theorem in [Frankl and Graham, European J. Combin. 1985] under certain circumstances. In the second part of this paper, we prove q-analogues of results on a recent notion called \emph{fractional L-intersecting family} for families of subspaces of a given vector space. We use the above theorem to obtain a general upper bound to the cardinality of such families. We give an improvement to this general upper bound in certain special cases.
A d-hypertree on [n] is a maximal acyclic d-dimensional simplicial complex with full (d−1)-skeleton on the vertex set [n]. Alternatively, in the language of algebraic topology, it is a minimal d-dimensional simplicial complex T (assuming full (d−1)-skeleton) such that H~d−1(T;F)=0. The d-hypertrees are a basic object in combinatorial theory of simplicial complexes. They have been studied; and yet, many of their structural aspects remain poorly understood. In this paper we study the boundaries ∂dT of d-hypertrees, and the fundamental d-cycles defined by them. Our findings include: 1. A full characterization of ∂dT over F2 for d≤2, and some partial results for d≥3. 2. Lower bounds on the maximum size of a largest simple d-cycle on [n]. In particular, for d=2, we construct a {\em Hamiltonian d-cycle} H on [n], i.e., a simple d-cycle of size (dn−1)+1. For d≥3, we construct a simple d-cycle of size (dn−1)−O(nd−2). 3. Observing that the maximum of the expected distance between two vertices chosen uniformly at random in a tree (1-hypertree) on [n] is at most ∼n/3, attained on Hamiltonian paths, we ask a similar question about d-hypertrees. "How large can be the {\em average} size of a fundamental cycle of a d-hypertree T (i.e., the expected size of the dependency created by adding a d-simplex on [n], chosen uniformly at random, to T)?" For every d∈N, we construct an infinite family of d-hypertrees {T} with the average size of a fundamental cycle at least cd∣T∣=cd(dn−1), where cd is a constant depending on the dimension d alone.
Given a graph G, a non-negative integer k, and a weight function that maps each vertex in G to a positive real number, the \emph{Maximum Weighted Budgeted Independent Set (MWBIS) problem} is about finding a maximum weighted independent set in G of cardinality at most k. A special case of MWBIS, when the weight assigned to each vertex is equal to its degree in G, is called the \emph{Maximum Independent Vertex Coverage (MIVC)} problem. In other words, the MIVC problem is about finding an independent set of cardinality at most k with maximum coverage. Since it is a generalization of the well-known Maximum Weighted Independent Set (MWIS) problem, MWBIS too does not have any constant factor polynomial time approximation algorithm assuming P=NP. In this paper, we study MWBIS in the context of bipartite graphs. We show that, unlike MWIS, the MIVC (and thereby the MWBIS) problem in bipartite graphs is NP-hard. Then, we show that the MWBIS problem admits a 21-factor approximation algorithm in the class of bipartite graphs, which matches the integrality gap of a natural LP relaxation.
A family F of permutations of the vertices of a hypergraph H is called 'pairwise suitable' for H if, for every pair of disjoint edges in H, there exists a permutation in F in which all the vertices in one edge precede those in the other. The cardinality of a smallest such family of permutations for H is called the 'separation dimension' of H and is denoted by π(H). Equivalently, π(H) is the smallest natural number k so that the vertices of H can be embedded in Rk such that any two disjoint edges of H can be separated by a hyperplane normal to one of the axes. We show that the separation dimension of a hypergraph H is equal to the 'boxicity' of the line graph of H. This connection helps us in borrowing results and techniques from the extensive literature on boxicity to study the concept of separation dimension.
We commence the study of domination in the incidence graphs of combinatorial designs. Let D be a combinatorial design and denote by γ(D) the domination number of the incidence (Levy) graph of D. We obtain a number of results about the domination numbers of various kinds of designs. For instance, a finite projective plane of order n, which is a symmetric (n2+n+1,n+1,1)-design, has γ=2n. %We also show that for any symmetric (v,k,λ)-design it holds that γ≤2k. We study at depth the domination numbers of Steiner systems and in particular of Steiner triple systems. We show that a STS(v) has γ≥32v−1 and also obtain a number of upper bounds. The tantalizing conjecture that all Steiner triple systems on v vertices have the same domination number is proposed and is verified up to v≤15. The structure of minimal dominating sets is also investigated, both for its own sake and as a tool in deriving lower bounds on γ. Finally, a number of open questions are proposed.
Let G be a graph on n vertices and let Lk be an arbitrary function that assigns each vertex in G a list of k colours. Then G is Lk-list colourable if there exists a proper colouring of the vertices of G such that every vertex is coloured with a colour from its own list. We say G is k-choosable if for every such function Lk, G is Lk-list colourable. The minimum k such that G is k-choosable is called the list chromatic number of G and is denoted by χL(G). Let χL(G)=s and let t be a positive integer less than s. The partial list colouring conjecture due to Albertson et al. \cite{albertson2000partial} states that for every Lt that maps the vertices of G to t-sized lists, there always exists an induced subgraph of G of size at least stn that is Lt-list colourable. In this paper we show that the partial list colouring conjecture holds true for certain classes of graphs like claw-free graphs, graphs with large chromatic number, chordless graphs, and series-parallel graphs. In the second part of the paper, we put forth a question which is a variant of the partial list colouring conjecture: does G always contain an induced subgraph of size at least stn that is t-choosable? We show that the answer to this question is not always `yes' by explicitly constructing an infinite family of 3-choosable graphs where a largest induced 2-choosable subgraph of each graph in the family is of size at most 85n.
The 'separation dimension' of a graph G is the smallest natural number k for which the vertices of G can be embedded in Rk such that any pair of disjoint edges in G can be separated by a hyperplane normal to one of the axes. Equivalently, it is the smallest possible cardinality of a family F of total orders of the vertices of G such that for any two disjoint edges of G, there exists at least one total order in F in which all the vertices in one edge precede those in the other. In general, the maximum separation dimension of a graph on n vertices is Θ(logn). In this article, we focus on bounded degree graphs and show that the separation dimension of a graph with maximum degree d is at most 29log⋆dd. We also demonstrate that the above bound is nearly tight by showing that, for every d, almost all d-regular graphs have separation dimension at least ⌈d/2⌉.
The separation dimension of a graph G is the smallest natural number k for which the vertices of G can be embedded in Rk such that any pair of disjoint edges in G can be separated by a hyperplane normal to one of the axes. Equivalently, it is the smallest possible cardinality of a family F of permutations of the vertices of G such that for any two disjoint edges of G, there exists at least one permutation in F in which all the vertices in one edge precede those in the other. In general, the maximum separation dimension of a graph on n vertices is Θ(logn). In this article, we focus on sparse graphs and show that the maximum separation dimension of a k-degenerate graph on n vertices is O(kloglogn) and that there exists a family of 2-degenerate graphs with separation dimension Ω(loglogn). We also show that the separation dimension of the graph G1/2 obtained by subdividing once every edge of another graph G is at most (1+o(1))loglogχ(G) where χ(G) is the chromatic number of the original graph.
The boxicity (respectively cubicity) of a graph G is the minimum non-negative integer k, such that G can be represented as an intersection graph of axis-parallel k-dimensional boxes (respectively k-dimensional unit cubes) and is denoted by box(G) (respectively cub(G)). It was shown by Adiga and Chandran (Journal of Graph Theory, 65(4), 2010) that for any graph G, cub(G)≤ box(G)⌈log2α⌉, where α=α(G) is the cardinality of the maximum independent set in G. In this note we show that cub(G)≤2⌈log2χ(G)⌉box(G)+χ(G)⌈log2α(G)⌉. In general, this result can provide a much better upper bound than that of Adiga and Chandran for graph classes with bounded chromatic number. For example, for bipartite graphs we get, cub(G)≤2(box(G)+⌈log2α(G)⌉). Moreover we show that for every positive integer k, there exist graphs with chromatic number k, such that for every ε>0, the value given by our upper bound is at most (1+ε) times their cubicity. Thus, our upper bound is almost tight.
The 'boxicity' ('cubicity') of a graph G is the minimum natural number k such that G can be represented as an intersection graph of axis-parallel rectangular boxes (axis-parallel unit cubes) in Rk. In this article, we give estimates on the boxicity and the cubicity of Cartesian, strong and direct products of graphs in terms of invariants of the component graphs. In particular, we study the growth, as a function of d, of the boxicity and the cubicity of the d-th power of a graph with respect to the three products. Among others, we show a surprising result that the boxicity and the cubicity of the d-th Cartesian power of any given finite graph is in O(logd/loglogd) and θ(d/logd), respectively. On the other hand, we show that there cannot exist any sublinear bound on the growth of the boxicity of powers of a general graph with respect to strong and direct products.
Characterization of k-chordal graphs based on the existence of a "simplicial path" was shown in [Chv{á}tal et al. Note: Dirac-type characterizations of graphs without long chordless cycles. Discrete Mathematics, 256, 445-448, 2002]. We give a characterization of k-chordal graphs which is a generalization of the known characterization of chordal graphs due to [G. A. Dirac. On rigid circuit graphs. Abh. Math. Sem. Univ. Hamburg, 25, 71-76, 1961] that use notions of a "simplicial vertex" and a "simplicial ordering".
Let k be an integer and k \geq 3. A graph G is k-chordal if G does not have an induced cycle of length greater than k. From the definition it is clear that 3-chordal graphs are precisely the class of chordal graphs. Duchet proved that, for every positive integer m, if G^m is chordal then so is G^{m+2}. Brandstädt et al. in [Andreas Brandstädt, Van Bang Le, and Thomas Szymczak. Duchet-type theorems for powers of HHD-free graphs. Discrete Mathematics, 177(1-3):9-16, 1997.] showed that if G^m is k-chordal, then so is G^{m+2}. Powering a bipartite graph does not preserve its bipartitedness. In order to preserve the bipartitedness of a bipartite graph while powering Chandran et al. introduced the notion of bipartite powering. This notion was introduced to aid their study of boxicity of chordal bipartite graphs. Given a bipartite graph G and an odd positive integer m, we define the graph G^{[m]} to be a bipartite graph with V(G^{[m]})=V(G) and E(G^{[m]})={(u,v) | u,v \in V(G), d_G(u,v) is odd, and d_G(u,v) \leq m}. The graph G^{[m]} is called the m-th bipartite power of G. In this paper we show that, given a bipartite graph G, if G is k-chordal then so is G^{[m]}, where k, m are positive integers such that k \geq 4 and m is odd.
A k-box B=(R1,...,Rk), where each Ri is a closed interval on the real line, is defined to be the Cartesian product R1×R2×...×Rk. If each Ri is a unit length interval, we call B a k-cube. Boxicity of a graph G, denoted as $\boxi(G)$, is the minimum integer k such that G is an intersection graph of k-boxes. Similarly, the cubicity of G, denoted as $\cubi(G)$, is the minimum integer k such that G is an intersection graph of k-cubes. It was shown in [L. Sunil Chandran, Mathew C. Francis, and Naveen Sivadasan: Representing graphs as the intersection of axis-parallel cubes. MCDES-2008, IISc Centenary Conference, available at CoRR, abs/cs/ 0607092, 2006.] that, for a graph G with maximum degree Δ, $\cubi(G)\leq \lceil 4(Δ+1)\log n\rceil$. In this paper, we show that, for a k-degenerate graph G, $\cubi(G) \leq (k+2) \lceil 2e \log n \rceil$. Since k is at most Δ and can be much lower, this clearly is a stronger result. This bound is tight. We also give an efficient deterministic algorithm that runs in O(n2k) time to output a 8k(⌈2.42logn⌉+1) dimensional cube representation for G. An important consequence of the above result is that if the crossing number of a graph G is t, then $\boxi(G)$ is O(t1/4⌈logt⌉3/4) . This bound is tight up to a factor of O((logt)1/4). We also show that, if G has n vertices, then $\cubi(G)$ is O(logn+t1/4logt). Using our bound for the cubicity of k-degenerate graphs we show that cubicity of almost all graphs in G(n,m) model is O(davlogn), where dav denotes the average degree of the graph under consideration.
A family F of permutations of the vertices of a hypergraph H is called "pairwise suitable" for H if, for every pair of disjoint edges in H, there exists a permutation in F in which all the vertices in one edge precede those in the other. The cardinality of a smallest such family of permutations for H is called the "separation dimension" of H and is denoted by π(H). Equivalently, π(H) is the smallest natural number k so that the vertices of H can be embedded in R^k such that any two disjoint edges of H can be separated by a hyperplane normal to one of the axes. We show that the separation dimension of a hypergraph H is equal to the "boxicity" of the line graph of H. This connection helps us in borrowing results and techniques from the extensive literature on boxicity to study the concept of separation dimension.
The product dimension of a graph G is defined as the minimum natural number l such that G is an induced subgraph of a direct product of l complete graphs. In this paper we study the product dimension of forests, bounded treewidth graphs and k-degenerate graphs. We show that every forest on n vertices has a product dimension at most 1.441logn+3. This improves the best known upper bound of 3logn for the same due to Poljak and Pultr. The technique used in arriving at the above bound is extended and combined with a result on existence of orthogonal Latin squares to show that every graph on n vertices with a treewidth at most t has a product dimension at most (t+2)(logn+1). We also show that every k-degenerate graph on n vertices has a product dimension at most \ceil{8.317klogn}+1. This improves the upper bound of 32klogn for the same by Eaton and Rodl.
We present two on-line algorithms for maintaining a topological order of a directed n-vertex acyclic graph as arcs are added, and detecting a cycle when one is created. Our first algorithm handles m arc additions in O(m3/2) time. For sparse graphs (m/n=O(1)), this bound improves the best previous bound by a logarithmic factor, and is tight to within a constant factor among algorithms satisfying a natural {\em locality} property. Our second algorithm handles an arbitrary sequence of arc additions in O(n5/2) time. For sufficiently dense graphs, this bound improves the best previous bound by a polynomial factor. Our bound may be far from tight: we show that the algorithm can take Ω(n222lgn) time by relating its performance to a generalization of the k-levels problem of combinatorial geometry. A completely different algorithm running in Θ(n2logn) time was given recently by Bender, Fineman, and Gilbert. We extend both of our algorithms to the maintenance of strong components, without affecting the asymptotic time bounds.
Rainbow connection number, rc(G), of a connected graph G is the minimum number of colours needed to colour its edges, so that every pair of vertices is connected by at least one path in which no two edges are coloured the same. In this paper we investigate the relationship of rainbow connection number with vertex and edge connectivity. It is already known that for a connected graph with minimum degree δ, the rainbow connection number is upper bounded by 3n/(δ+1)+3 [Chandran et al., 2010]. This directly gives an upper bound of 3n/(λ+1)+3 and 3n/(κ+1)+3 for rainbow connection number where λ and κ, respectively, denote the edge and vertex connectivity of the graph. We show that the above bound in terms of edge connectivity is tight up-to additive constants and show that the bound in terms of vertex connectivity can be improved to (2+ε)n/κ+23/ε2, for any ε>0. We conjecture that rainbow connection number is upper bounded by n/κ+O(1) and show that it is true for κ=2. We also show that the conjecture is true for chordal graphs and graphs of girth at least 7.
Boxicity of a graph H, denoted by box(H), is the minimum integer k such that H is an intersection graph of axis-parallel k-dimensional boxes in R^k. In this paper, we show that for a line graph G of a multigraph, box(G) <= 2Δ(\lceil log_2(log_2(Δ)) \rceil + 3) + 1, where Δdenotes the maximum degree of G. Since Δ<= 2(χ- 1), for any line graph G with chromatic number χ, box(G) = O(χlog_2(log_2(χ))). For the d-dimensional hypercube H_d, we prove that box(H_d) >= (\lceil log_2(log_2(d)) \rceil + 1)/2. The question of finding a non-trivial lower bound for box(H_d) was left open by Chandran and Sivadasan in [L. Sunil Chandran and Naveen Sivadasan. The cubicity of Hypercube Graphs. Discrete Mathematics, 308(23):5795-5800, 2008]. The above results are consequences of bounds that we obtain for the boxicity of fully subdivided graphs (a graph which can be obtained by subdividing every edge of a graph exactly once).
Research graph
Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.
BZPEER is loading the nearby papers, people, topics and institutions for this page.