HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Could a directed graph be bipartite?

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
bipartitedirectedcouldgraph

Problem

I check for the symmetric directed graph and it's impossible to be bipartite , because we can't divide the vertices into two sets since all will have in - and out arrow
but in general it could be right ?
if I draw a graph with one direction

Solution

The monograph Digraphs: Theory, Algorithms and Applications by Bang-Jensen and Gutin defines a bipartite digraph as a digraph whose vertices can be partitioned into two sets $A,B$ such that every directed edge connects a vertex in $A$ to a vertex in $B$ or vice versa. Alternatively, a bipartite digraph is a digraph which can be obtained from a bipartite graph by replacing each undirected edge by a directed edge or by a pair of directed edges.

In some situations we might want to add the condition that there are no parallel edges, that is, that it if $(x,y)$ is an edge then $(y,x)$ is not an edge.

Context

StackExchange Computer Science Q#91519, answer score: 9

Revisions (0)

No revisions yet.