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.
We introduce a generalization of "Solo Chess", a single-player variant of the game that can be played on chess.com. The standard version of the game is played on a regular 8 x 8 chessboard by a single player, with only white pieces, using the following rules: every move must capture a piece, no piece may capture more than 2 times, and if there is a King on the board, it must be the final piece. The goal is to clear the board, i.e, make a sequence of captures after which only one piece is left. We generalize this game to unbounded boards with n pieces, each of which have a given number of captures that they are permitted to make. We show that Generalized Solo Chess is NP-complete, even when it is played by only rooks that have at most two captures remaining. It also turns out to be NP-complete even when every piece is a queen with exactly two captures remaining in the initial configuration. In contrast, we show that solvable instances of Generalized Solo Chess can be completely characterized when the game is: a) played by rooks on a one-dimensional board, and b) played by pawns with two captures left on a 2D board. Inspired by Generalized Solo Chess, we also introduce the Graph Capture Game, which involves clearing a graph of tokens via captures along edges. This game subsumes Generalized Solo Chess played by knights. We show that the Graph Capture Game is NP-complete for undirected graphs and DAGs.
Motivated by a recent conjecture of the first author, we prove that every properly coloured triangle-free graph of chromatic number χ contains a rainbow independent set of size ⌈21χ⌉. This is sharp up to a factor 2. This result and its short proof have implications for the related notion of chromatic discrepancy. Drawing inspiration from both structural and extremal graph theory, we conjecture that every triangle-free graph of chromatic number χ contains an induced cycle of length Ω(χlogχ) as χ→∞. Even if one only demands an induced path of length Ω(χlogχ), the conclusion would be sharp up to a constant multiple. We prove it for regular girth 5 graphs and for girth 21 graphs. As a common strengthening of the induced paths form of this conjecture and of Johansson's theorem (1996), we posit the existence of some c>0 such that for every forest H on D vertices, every triangle-free and induced H-free graph has chromatic number at most cD/logD. We prove this assertion with `triangle-free' replaced by `regular girth 5'.
We introduce and study the notion of read-k projections of the determinant: a polynomial f∈F[x1,…,xn] is called a {\it read-k projection of determinant} if f=det(M), where entries of matrix M are either field elements or variables such that each variable appears at most k times in M. A monomial set S is said to be expressible as read-k projection of determinant if there is a read-k projection of determinant f such that the monomial set of f is equal to S. We obtain basic results relating read-k determinantal projections to the well-studied notion of determinantal complexity. We show that for sufficiently large n, the n×n permanent polynomial Permn and the elementary symmetric polynomials of degree d on n variables Snd for 2≤d≤n−2 are not expressible as read-once projection of determinant, whereas mon(Permn) and mon(Snd) are expressible as read-once projections of determinant. We also give examples of monomial sets which are not expressible as read-once projections of determinant.
For a graph H, the H-free Edge Deletion problem asks whether there exist at most k edges whose deletion from the input graph G results in a graph without any induced copy of H. We prove that H-free Edge Deletion is NP-complete if H is a graph with at least two edges and H has a component with maximum number of vertices which is a tree or a regular graph. Furthermore, we obtain that these NP-complete problems cannot be solved in parameterized subexponential time, i.e., in time 2o(k)⋅∣G∣O(1), unless Exponential Time Hypothesis fails.
For a graph H, the H-free Edge Deletion problem asks whether there exist at most k edges whose deletion from the input graph G results in a graph without any induced copy of H. H-free Edge Completion and H-free Edge Editing are defined similarly where only completion (addition) of edges are allowed in the former and both completion and deletion are allowed in the latter. We completely settle the classical complexities of these problems by proving that H-free Edge Deletion is NP-complete if and only if H is a graph with at least two edges, H-free Edge Completion is NP-complete if and only if H is a graph with at least two non-edges and H-free Edge Editing is NP-complete if and only if H is a graph with at least three vertices. Additionally, we prove that, these NP-complete problems cannot be solved in parameterized subexponential time, i.e., in time 2o(k)⋅∣G∣O(1), unless Exponential Time Hypothesis fails. Furthermore, we obtain implications on the incompressibility of these problems.
For a set of graphs H, the \textsc{H-free Edge Deletion} problem asks to find whether there exist at most k edges in the input graph whose deletion results in a graph without any induced copy of H∈H. In \cite{cai1996fixed}, it is shown that the problem is fixed-parameter tractable if H is of finite cardinality. However, it is proved in \cite{cai2013incompressibility} that if H is a singleton set containing H, for a large class of H, there exists no polynomial kernel unless coNP⊆NP/poly. In this paper, we present a polynomial kernel for this problem for any fixed finite set H of connected graphs and when the input graphs are of bounded degree. We note that there are \textsc{H-free Edge Deletion} problems which remain NP-complete even for the bounded degree input graphs, for example \textsc{Triangle-free Edge Deletion}\cite{brugmann2009generating} and \textsc{Custer Edge Deletion(P3-free Edge Deletion)}\cite{komusiewicz2011alternative}. When H contains K1,s, we obtain a stronger result - a polynomial kernel for Kt-free input graphs (for any fixed t>2). We note that for s>9, there is an incompressibility result for \textsc{K1,s-free Edge Deletion} for general graphs \cite{cai2012polynomial}. Our result provides first polynomial kernels for \textsc{Claw-free Edge Deletion} and \textsc{Line Edge Deletion} for Kt-free input graphs which are NP-complete even for K4-free graphs\cite{yannakakis1981edge} and were raised as open problems in \cite{cai2013incompressibility,open2013worker}.
For a proper vertex coloring c of a graph G, let φc(G) denote the maximum, over all induced subgraphs H of G, the difference between the chromatic number χ(H) and the number of colors used by c to color H. We define the chromatic discrepancy of a graph G, denoted by φ(G), to be the minimum φc(G), over all proper colorings c of G. If H is restricted to only connected induced subgraphs, we denote the corresponding parameter by φ^(G). These parameters are aimed at studying graph colorings that use as few colors as possible in a graph and all its induced subgraphs. We study the parameters φ(G) and φ^(G) and obtain bounds on them. We obtain general bounds, as well as bounds for certain special classes of graphs including random graphs. We provide structural characterizations of graphs with φ(G)=0 and graphs with φ^(G)=0. We also show that computing these parameters is NP-hard.
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.