Variation on a theorem of König (Q797595)

From MaRDI portal
scientific article
Language Label Description Also known as
English
Variation on a theorem of König
scientific article

    Statements

    Variation on a theorem of König (English)
    0 references
    0 references
    1984
    0 references
    Let G be a bipartite graph. Two disjoint subsets \(F_ 1\), \(F_ 2\) of the edge set of G are said to form an equitable pair if, for each node x of G, the numbers of edges in \(F_ 1\), resp. \(F_ 2\) incident with x differ by at most one. An S-cover s of G is a subset S of nodes in G together with all edges having either both nodes or no node in S. Using network flow technique it is proved that, for G bipartite, \(\max \{| F_ 1| -| F_ 2|; F_ 1,F_ 2\) equitable pair in \(G\}= \min\{| s|;\) s an S-cover in G\}.
    0 references
    maximum degree
    0 references
    equitable colourings
    0 references
    bipartite graph
    0 references
    equitable pair
    0 references
    0 references
    0 references
    0 references

    Identifiers