Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userGraphs with polynomially many minimal separators
301
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
We show that graphs that do not contain a theta, pyramid, prism, or turtle as an induced subgraph have polynomially many minimal separators. This result is the best possible in the sense that there are graphs with exponentially many minimal separators if only three of the four induced subgraphs are excluded. As a consequence, there is a polynomial time algorithm to solve the maximum weight independent set problem for the class of (theta, pyramid, prism, turtle)-free graphs. Since every prism, theta, and turtle contains an even hole, this also implies a polynomial time algorithm to solve the maximum weight independent set problem for the class of (pyramid, even hole)-free graphs.
rate research
Read More
Given any graph $H$, a graph $G$ is said to be $q$-Ramsey for $H$ if every coloring of the edges of $G$ with $q$ colors yields a monochromatic subgraph isomorphic to $H$. Further, such a graph $G$ is said to be minimal $q$-Ramsey for $H$ if additionally no proper subgraph $G$ of $G$ is $q$-Ramsey for $H$. In 1976, Burr, ErdH{o}s, and Lovasz initiated the study of the parameter $s_q(H)$, defined as the smallest minimum degree among all minimal $q$-Ramsey graphs for $H$. In this paper, we consider the problem of determining how many vertices of degree $s_q(H)$ a minimal $q$-Ramsey graph for $H$ can contain. Specifically, we seek to identify graphs for which a minimal $q$-Ramsey graph can contain arbitrarily many such vertices. We call a graph satisfying this property $s_q$-abundant. Among other results, we prove that every cycle is $s_q$-abundant for any integer $qgeq 2$. We also discuss the cases when $H$ is a clique or a clique with a pendant edge, extending previous results of Burr et al. and Fox et al. To prove our results and construct suitable minimal Ramsey graphs, we develop certain new gadget graphs, called pattern gadgets, which generalize and extend earlier constructions that have proven useful in the study of minimal Ramsey graphs. These new gadgets might be of independent interest.
A grounded L-graph is the intersection graph of a collection of L shapes whose topmost points belong to a common horizontal line. We prove that every grounded L-graph with clique number $omega$ has chromatic number at most $17omega^4$. This improves the doubly-exponential bound of McGuinness and generalizes the recent result that the class of circle graphs is polynomially $chi$-bounded. We also survey $chi$-boundedness problems for grounded geometric intersection graphs and give a high-level overview of recent techniques to obtain polynomial bounds.
We establish mild conditions under which a possibly irregular, sparse graph $G$ has many strong orientations. Given a graph $G$ on $n$ vertices, orient each edge in either direction with probability $1/2$ independently. We show that if $G$ satisfies a minimum degree condition of $(1+c_1)log_2{n}$ and has Cheeger constant at least $c_2frac{log_2log_2{n}}{log_2{n}}$, then the resulting randomly oriented directed graph is strongly connected with high probability. This Cheeger constant bound can be replaced by an analogous spectral condition via the Cheeger inequality. Additionally, we provide an explicit construction to show our minimum degree condition is tight while the Cheeger constant bound is tight up to a $log_2log_2{n}$ factor.
In the online labeling problem with parameters n and m we are presented with a sequence of n keys from a totally ordered universe U and must assign each arriving key a label from the label set {1,2,...,m} so that the order of labels (strictly) respects the ordering on U. As new keys arrive it may be necessary to change the labels of some items; such changes may be done at any time at unit cost for each change. The goal is to minimize the total cost. An alternative formulation of this problem is the file maintenance problem, in which the items, instead of being labeled, are maintained in sorted order in an array of length m, and we pay unit cost for moving an item. For the case m=cn for constant c>1, there are known algorithms that use at most O(n log(n)^2) relabelings in total [Itai, Konheim, Rodeh, 1981], and it was shown recently that this is asymptotically optimal [Bulanek, Koucky, Saks, 2012]. For the case of m={Theta}(n^C) for C>1, algorithms are known that use O(n log n) relabelings. A matching lower bound was claimed in [Dietz, Seiferas, Zhang, 2004]. That proof involved two distinct steps: a lower bound for a problem they call prefix bucketing and a reduction from prefix bucketing to online labeling. The reduction seems to be incorrect, leaving a (seemingly significant) gap in the proof. In this paper we close the gap by presenting a correct reduction to prefix bucketing. Furthermore we give a simplified and improved analysis of the prefix bucketing lower bound. This improvement allows us to extend the lower bounds for online labeling to the case where the number m of labels is superpolynomial in n. In particular, for superpolynomial m we get an asymptotically optimal lower bound {Omega}((n log n) / (log log m - log log n)).
Let $S(G^sigma)$ be the skew-adjacency matrix of an oriented graph $G^sigma$. The skew energy of $G^sigma$ is defined as the sum of all singular values of its skew-adjacency matrix $S(G^sigma)$. In this paper, we first deduce an integral formula for the skew energy of an oriented graph. Then we determine all oriented graphs with minimal skew energy among all connected oriented graphs on $n$ vertices with $m (nle m < 2(n-2))$ arcs, which is an analogy to the conjecture for the energy of undirected graphs proposed by Caporossi {it et al.} [G. Caporossi, D. Cvetkovi$acute{c}$, I. Gutman, P. Hansen, Variable neighborhood search for extremal graphs. 2. Finding graphs with external energy, J. Chem. Inf. Comput. Sci. 39 (1999) 984-996.]
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
