# Tag Info

8

The famous graph (the complement of the disjoint union of $n/3$ triangles) with $3^{n/3}$ maximal cliques is $K_1 \cup K_2$-free, and thus has none of $2C_4$, $C_5$, $P_5$ as an induced subgraph. https://doi.org/10.1007/BF02760024

7

The two-connected series-parallel DAGs are also called 2-terminal series-parallel graphs. The graph in the figure is also known as Wheatstone graph and is known as the example graph for demonstrating Braess' paradox in algorithmic game theory. It was shown [1, Theorem 5.3] that a DAG is 2-terminal series-parallel if and only if it does not contain a subgraph ...

5

It is known that a graph of treewidth $k$ and maximum degree $\Delta$ has tree partition width at most $O(k\Delta)$. See Wood, arXiv:math/0602507. From a tree partition of width $O(k\Delta)$ a triangulation of width $O(k\Delta)$ and maximum degree $O(k\Delta^2)$ follows pretty directly (start with the tree partition, make every bag into a clique, make every ...

4

For arbitrarily large number $n$ of variables, the following CNF formula $\phi$ is not satisfiable, has only three clauses, and a $2K_2$-free clause-variable incidence graph: $C_1=(x_1)$, $C_2=(\neg x_1)$, $C_3=(x_1,\ldots,x_n)$. Thus, to get more interesting lower bounds one needs to make assumption about the minimum clause size or about the size of classes ...

3

In this answer i assume that $u$ is an ancestor of $v$ if $u$ can reach $v$ by a directed path. This is basically as hard as Set Cover (Given family $F$ over a universe $U$, find smallest subfamily $F’$ of $F$ whose union is $U$). To reduce from Set Cover: Make a vertex for every set in $F$ and for every element in $U$. Make an arc from every element to ...

2

Here is a very slow algorithm, but it handles more general cases, like when density is defined as $d_\beta(G) = \frac{m(G)}{n(G)-\beta}$. Let $f$ be a submodular function, $g$ be a modular function strictly larger than $0$. The min ratio problem $\min_S f(S)/g(S)$ can be solved in polynomial time. Indeed, use the standard to convert min ratio problem to ...

1

Conjecture 2 is already proved. Quote from J.A. Tilley, The a-graph coloring problem(2017): Theorem A.1. Let $G$ be an a-graph with boundary cycle $uxvy$ for the exterior 4-face and let $G$ have a 4-coloring $c$. Suppose, without loss of generality, that $c(x)=1$, $c(y)=1$ or 2, $c(u)=3$, and $c(v)=3$ or 4. Then there is either a 1–2 path between $x$ and $y$...

Only top voted, non community-wiki answers of a minimum length are eligible