Sandwich problem for Π- and Δ-free multigraphs and its applications to positional games

Discrete Mathematics. 2015. Vol. 338. No. 12. P. 2421–2436.

Gurvich V., Boros E.

An n-multigraph  G=(V;Ei∣i∈I) is a complete graph G=(V,E) whose edges are covered by n=|I| sets, E=∪i∈IEi, some of which might be empty. If this cover is a partition, then G is called an n-graph  . We say that an n-graph  is an edge subgraph of an n-multigraph G=(V;Ei∣i∈I) if  for all i∈I. We denote by Δthe n-graph on three vertices with three nonempty sets each containing a single edge, and by Π the four-vertex n-graph with two non-empty sets each of which contains the edges of a P4. In this paper, we recognize in polynomial time whether a given n-multigraph G contains a Π- and Δ-free n-subgraph, or not, and if yes, provide a polynomial delay algorithm generating all such subgraphs. The above decision problem can be viewed as a generalization of the sandwich problem for P4-free graphs solved by Golumbic et al. (1995).

 

As a motivation and application, we consider the n-person positional game forms, which are known to be in a one-to-one correspondence with the Π- and Δ-free n-graphs. Given a game form g, making use of the above result, we recognize in polynomial time whetherg is a subform of a positional (that is, tight and rectangular) game form and, if yes, we generate with polynomial delay all such positional extensions of g.

Keywords: Edge-colored n-graph, Gallai graph, Sandwich problem