[Disclaimer: this a blog-post consciously written in the style adumbrated in Compressing and summarizing. Part 0. For the original, see https://arxiv.org/abs/1707.09400. Compression ratio here is high. ]

This recent preprint of Jørgen Bang-Jensen, Stéphane Bessy, Frédéric Havet, Anders Yeo on digraphs is very interesting to me, because

- I am recently quite involved in digraph-theory for more than one reason,
- since student-days I am very interested in max-cut-like problems like the folklore classic recalled in Prop. 1. of loc. cit.

so I’ll here report on loc.cit.

For further reference, we introduce notation:

- Let denote the full subcategory of the category of digraphs which is spanned by the
*bipartite* digraphs. For each digraph let denote the full subcategory of spanned by the *spanning bipartite subdigraphs of *. Let denote the power-set of the set , considered as a posetal category in the usual way. Central concept of loc. cit. is, for each digraph , a functor

which in particular takes any to digraph .

Graph here means undirected simple graph.

For brevity,

- ‘isol.-free.’ is an abbreviation for ‘is free of isolated vertices'(has minimum degree at least one),
- ‘-bipartition’ is an abbreviation for ‘bipartition of the vertex set of the graph such that each vertex in has at least neighbours in . Loc. cit. Problem 2 denotes this by the longer ‘-bipartite partition’.

On a pedantic note, it seems an improvement to replace the formulation ‘bipartite-partition’ of loc. cit. with ‘bipartition’, since strictly speaking a ‘bipartite partition’ is not defined in graph theory, and since my alternative suggestion is even shorter than the original.

Prop. 1 loc. cit. recalls the fact that every *finite* graph admits an *unfriendly partition*. Loc. cit. then points out that this implies that every finite isol.-free graph admits a partition such that the bipartite graph defined by it is itself isol.-free. This of course implies that there is a time algorithm to decide if an $n$-vertex graph admits a -bipartition.

Loc. cit. then states the more general class of decision problems

- – given a finite graph, to decide whether it admits at least one -bipartition.

Loc. cit. inter alia gives a proof that

- if , then – admits an algorithm polynomial in the order of the input graph,
- if , then – is NP-complete.

To be continued.

### Like this:

Like Loading...

*Related*