Problems

A graph is K 5-friendly if and only if it does not contain any of K_6,C_7^2 and DW_5 as a minor.

Here is another variant that is open. In this case we begin with a -1, +1 valued matrix with discrepancy n^3/2. Say a Hadamard matrix. Balancer picks certain +1's. Unbalancer picks certain -1's. Over the course of the game, can Balancer…

Does this set contain interior points within the manifold A ∈ R_+^m × n | rk A = k of nonnegative rank-k matrices?

If vecG is a best-balanced orientation of G := (V + s, E) and varrho_vecG(s) = δ_vecG(s) then there exist rs, st ∈ A(vecG) so that vecG_rt is a best-balanced orientation of G_rt.

For every graph G = (V + s, E) with d(s) ≥ 4 there exist rs, st ∈ E such that for every best-balanced orientation vecG_rt of G_rt, vecG := vecG_rt - rt + rs + st is a best-balanced orientation of G.

Let b: V → Z_0^+ be a symmetric crossing submodular function with b(∅) = 0 and b(X) ≡ |X ∩ T_b| mod 2. Then there exists a pairing M on T_b that satisfies (17).

We believe that results similar to Theorem 4.3.5 can be proved for intersection graphs of other scalable objects. In particular, we conjecture that similar techniques apply to intersection graphs of (unit) regular hexagons.

An interesting open question is whether L(p, 1)-LABELING parameterized by only twin cover number is FPT or not.

Let d: V → Z_0^+ be a symmetric function that satisfies d(∅) = 0 and ∀ X, Y ⊆ V (19) and (20). Let hatR: V → Z_0^+ be an even valued, symmetric, skew-supermodular function. Suppose that hatR(X) ≤ d(X) ∀ X ⊆ V. Then there exists a pairing M…