36:
25:
71:
1601:
1464:
type it should check that these two vertices have different colors. If they do not, then the path in the forest from ancestor to descendant, together with the miscolored edge, form an odd cycle, which is returned from the algorithm together with the result that the graph is not bipartite. However, if the algorithm terminates without detecting an odd cycle of this type, then every edge must be properly colored, and the algorithm returns the coloring together with the result that the graph is bipartite.
51:
794:, in such a way that two vertices are adjacent if and only if the corresponding bitvectors differ in a single position. A bipartition may be formed by separating the vertices whose bitvectors have an even number of ones from the vertices with an odd number of ones. Trees and squaregraphs form examples of median graphs, and every median graph is a partial cube.
1381:(a graph in which there may be two or more edges between the same two vertices) may be interpreted as a hypergraph in which some hyperedges have equal sets of endpoints, and represented by a bipartite graph that does not have multiple adjacencies and in which the vertices on one side of the bipartition all have
1901:
are examples of this. A Tanner graph is a bipartite graph in which the vertices on one side of the bipartition represent digits of a codeword, and the vertices on the other side represent combinations of digits that are expected to sum to zero in a codeword without errors. A factor graph is a closely
874:
plus the size of a maximum matching equals the number of vertices. Combining this equality with KĹ‘nig's theorem leads to the facts that, in bipartite graphs, the size of the minimum edge cover is equal to the size of the maximum independent set, and the size of the minimum edge cover plus the size of
902:
of bipartite graphs is less trivial, and is another restatement of KĹ‘nig's theorem. This was one of the results that motivated the initial definition of perfect graphs. Perfection of the complements of line graphs of perfect graphs is yet another restatement of KĹ‘nig's theorem, and perfection of the
1921:
is a mathematical modeling tool used in analysis and simulations of concurrent systems. A system is modeled as a bipartite directed graph with two sets of nodes: A set of "place" nodes that contain resources, and a set of "event" nodes which generate and/or consume resources. There are additional
1471:
in place of depth-first search. Again, each node is given the opposite color to its parent in the search forest, in breadth-first order. If, when a vertex is colored, there exists an edge connecting it to a previously-colored vertex with the same color, then this edge together with the paths in the
1463:
consisting of the edges connecting vertices to their parents, but it may not properly color some of the non-forest edges. In a depth-first search forest, one of the two endpoints of every non-forest edge is an ancestor of the other endpoint, and when the depth first search discovers an edge of this
926:. The bipartite graphs, line graphs of bipartite graphs, and their complements form four out of the five basic classes of perfect graphs used in the proof of the strong perfect graph theorem. It follows that any subgraph of a bipartite graph is also bipartite because it cannot gain an odd cycle.
1922:
constraints on the nodes and edges that constrain the behavior of the system. Petri nets utilize the properties of bipartite directed graphs and other properties to allow mathematical proofs of the behavior of systems while also allowing easy implementation of simulations of the system.
619:) railway optimization problem, in which the input is a schedule of trains and their stops, and the goal is to find a set of train stations as small as possible such that every train visits at least one of the chosen stations. This problem can be modeled as a
1197:
is the problem of finding a simple bipartite graph with the degree sequence being two given lists of natural numbers. (Trailing zeros may be ignored since they are trivially realized by adding an appropriate number of isolated vertices to the digraph.)
603:
between two different classes of objects, bipartite graphs very often arise naturally. For instance, a graph of football players and clubs, with an edge between a player and a club if the player has played for that club, is a natural example of an
626:
A third example is in the academic field of numismatics. Ancient coins are made using two positive impressions of the design (the obverse and reverse). The charts numismatists produce to represent the production of coins are bipartite graphs.
1937:. Corresponding to the geometric property of points and lines that every two lines meet in at most one point and every two points be connected with a single line, Levi graphs necessarily do not contain any cycles of length four, so their
1189:
bipartite graphs have the same degree sequence. However, the degree sequence does not, in general, uniquely identify a bipartite graph; in some cases, non-isomorphic bipartite graphs may have the same degree sequence.
1392:(on a given number of labeled vertices, allowing self-loops) and balanced bipartite graphs, with the same number of vertices on both sides of the bipartition. For, the adjacency matrix of a directed graph with
1306:
is a combinatorial structure that, like an undirected graph, has vertices and edges, but in which the edges may be arbitrary sets of vertices rather than having to have exactly two endpoints. A bipartite graph
1059:
1298:
that has a one for each pair of adjacent vertices and a zero for nonadjacent vertices. Biadjacency matrices may be used to describe equivalences between bipartite graphs, hypergraphs, and directed graphs.
1669:
problem is the algorithmic problem of deleting as few edges as possible to make a graph bipartite and is also an important problem in graph modification algorithmics. This problem is also
336:
red, each edge has endpoints of differing colors, as is required in the graph coloring problem. In contrast, such a coloring is impossible in the case of a non-bipartite graph, such as a
1476:
forms an odd cycle. If the algorithm terminates without finding an odd cycle in this way, then it must have found a proper coloring, and can safely conclude that the graph is bipartite.
3091:
Guo, Jiong; Gramm, Jens; HĂĽffner, Falk; Niedermeier, Rolf; Wernicke, Sebastian (2006), "Compression-based fixed-parameter algorithms for feedback vertex set and edge bipartization",
1721:
1662:
set. In the illustration, every odd cycle in the graph contains the blue (the bottommost) vertices, so removing those vertices kills all odd cycles and leaves a bipartite graph.
1584:
1183:
918:
resembling that of bipartite graphs: a graph is bipartite if and only if it has no odd cycle as a subgraph, and a graph is perfect if and only if it has no odd cycle or its
1296:
340:: after one node is colored blue and another red, the third vertex of the triangle is connected to vertices of both colors, preventing it from being assigned either color.
1546:
1424:
727:
385:
2013:, a type of Steiner tree problem instance in which the terminals form an independent set, allowing approximation algorithms that generalize those for bipartite graphs
1848:
1343:
1246:
533:
487:
962:
1810:
1790:
1501:
1102:
1082:
585:
557:
445:
425:
405:
334:
314:
290:
270:
239:
219:
199:
179:
151:
131:
890:
of every bipartite graph, and the complement of the line graph of every bipartite graph, are all perfect. Perfection of bipartite graphs is easy to see (their
623:
problem in a bipartite graph that has a vertex for each train and each station and an edge for each pair of a station and a train that stops at that station.
1646:, meaning that there is an algorithm whose running time can be bounded by a polynomial function of the size of the graph multiplied by a larger function of
1455:. The main idea is to assign to each vertex the color that differs from the color of its parent in the depth-first search forest, assigning colors in a
1765:. In many cases, matching problems are simpler to solve on bipartite graphs than on non-bipartite graphs, and many matching algorithms such as the
1658:. Hence, to delete vertices from a graph in order to obtain a bipartite graph, one needs to "hit all odd cycle", or find a so-called odd cycle
1447:
It is possible to test whether a graph is bipartite, and to return either a two-coloring (if it is bipartite) or an odd cycle (if it is not) in
2257:
Judaea and Rome in Coins 65 BCE – 135 CE: Papers
Presented at the International Conference hosted by Spink, 13th – 14th September 2010
974:
3137:, p. 463: "Nonbipartite matching problems are more difficult to solve because they do not reduce to standard network flow problems."
2019:, a graph in which the vertices can be partitioned into two subsets, one of which is independent and the other of which is a clique
2255:
Bracey, Robert (2012), "On the graphical interpretation of Herod's year 3 coins", in
Jacobson, David M.; Kokkinos, Nikos (eds.),
1863:
2908:
2288:
2240:
2057:
1207:
2467:
2318:
1874:
859:
1377:
of the corresponding hypergraphs. As a special case of this correspondence between bipartite graphs and hypergraphs, any
1859:
3333:
3295:
3256:
2775:
2651:
2621:
2587:
2537:
2461:
2212:
2182:
2148:
2096:
3010:
915:
3198:
3321:
1510:, it is possible to test whether the graph is bipartite and return either a two-coloring or an odd cycle in time
1604:
A graph with an odd cycle transversal of size 2: removing the two blue bottom vertices leaves a bipartite graph.
2671:
2492:
2384:
2278:
111:
2063:
489:
notation is helpful in specifying one particular bipartition that may be of importance in an application. If
3422:
3362:
3325:
2813:
2294:. This result has sometimes been called the "two color theorem"; Soifer credits it to a famous 1879 paper of
2049:
1194:
2679:
2675:
1982:
1064:
The degree sequence of a bipartite graph is the pair of lists each containing the degrees of the two parts
911:
99:
1676:
903:
line graphs themselves is a restatement of an earlier theorem of KĹ‘nig, that every bipartite graph has an
3357:
2808:
2607:
2207:, Structural Analysis in the Social Sciences, vol. 8, Cambridge University Press, pp. 299–302,
2168:
1766:
1659:
1551:
1388:
A similar reinterpretation of adjacency matrices may be used to show a one-to-one correspondence between
1114:
652:
3043:
1855:
1812:
of jobs, with not all people suitable for all jobs. This situation can be modeled as a bipartite graph
3352:
2235:, Oxford Lecture Series in Mathematics and Its Applications, Oxford University Press, pp. 20–21,
3417:
1890:
1670:
919:
899:
883:
3060:
2708:
3397:
1934:
1643:
1255:
667:
55:
3119:
Ahuja, Ravindra K.; Magnanti, Thomas L.; Orlin, James B. (1993), "12. Assignments and
Matchings",
663:, in which every inner face consists of 4 edges and every inner vertex has four or more neighbors.
3412:
2832:
1991:, a bipartite graph whose vertices can be ordered so that the vertex neighborhoods are contiguous
1758:
1746:
1740:
863:
609:
337:
2803:
1513:
3055:
2703:
1988:
1956:
1877:
is a structural decomposition of bipartite graphs that is useful in finding maximum matchings.
1473:
1431:
1403:
866:
plus the size of the maximum matching is equal to the number of vertices. In any graph without
688:
600:
346:
3285:
3246:
2765:
2641:
2611:
2577:
2202:
2172:
2138:
245:
of the graph. Equivalently, a bipartite graph is a graph that does not contain any odd-length
3315:
2684:
2527:
2010:
1815:
1608:
1595:
1382:
1310:
1213:
935:
838:
564:
492:
454:
158:
103:
2761:
941:
3077:
2984:
2886:
2853:
2513:
2022:
1962:
1938:
1867:
1655:
1468:
1430:
vertices on each side of its bipartition. In this construction, the bipartite graph is the
851:
817:
246:
2740:
2429:, Theorem 2.1.3, p. 8. Asratian et al. attribute this characterization to a 1916 paper by
1373:. Under this correspondence, the biadjacency matrices of bipartite graphs are exactly the
8:
2532:, Cambridge Mathematical Library (2nd ed.), Cambridge University Press, p. 53,
2382:; Gavlas, H. (2004), "Cycle systems in the complete bipartite graph minus a one-factor",
1950:
1933:
are a form of bipartite graph used to model the incidences between points and lines in a
1926:
834:, minimal subsets of edges whose removal increases the number of components of the graph.
635:
154:
3026:
3006:
2988:
2962:
2890:
2721:
2693:
2637:
2345:
2327:
2299:
2085:
1994:
1858:
provides a characterization of the bipartite graphs which allow perfect matchings. The
1795:
1775:
1486:
1480:
1456:
1452:
1087:
1067:
965:
871:
831:
570:
542:
430:
410:
390:
319:
299:
275:
255:
224:
204:
184:
164:
136:
116:
35:
3311:
1459:
of the depth-first-search forest. This will necessarily provide a two-coloring of the
3380:
3329:
3291:
3252:
2894:
2860:
2771:
2725:
2647:
2617:
2583:
2533:
2505:
2457:
2284:
2236:
2208:
2198:
2178:
2144:
2092:
2053:
1972:
1186:
24:
3384:
2582:, Discrete Mathematics And Its Applications (2nd ed.), CRC Press, p. 568,
2349:
1426:, which can then be reinterpreted as the adjacency matrix of a bipartite graph with
70:
3167:
3100:
3065:
3016:
2972:
2872:
2841:
2713:
2667:
2553:
2501:
2430:
2393:
2337:
2274:
2228:
2177:, Discrete Mathematics And Its Applications, vol. 53, CRC Press, p. 223,
1854:
describes a way of simultaneously satisfying all job-seekers and filling all jobs;
1851:
1754:
1374:
923:
891:
855:
824:
773:
563:
bipartite graph. If all vertices on the same side of the bipartition have the same
3030:
1600:
3373:
3073:
2992:
2980:
2882:
2849:
2509:
2490:
Woodall, D. R. (1990), "A proof of McKee's
Eulerian-bipartite characterization",
2448:
2434:
1976:
1959:, a way of transforming any graph into a bipartite graph by doubling its vertices
1762:
1750:
1507:
1460:
867:
779:
588:
448:
1953:, the minimum number of complete bipartite graphs whose union is the given graph
3105:
2950:
2717:
2603:
2397:
2375:
2313:
2260:
2164:
2134:
1903:
1389:
895:
813:
620:
293:
3069:
2091:, Cambridge Tracts in Mathematics, vol. 131, Cambridge University Press,
3406:
3147:
2927:
1886:
904:
879:
862:. An alternative and equivalent form of this theorem is that the size of the
107:
75:
2976:
2931:
2025:
on the maximum number of edges in a bipartite graph with forbidden subgraphs
1985:, a weighting technique for compressing information about bipartite networks
3151:
2877:
2845:
2827:
2295:
2004:
2000:
1997:, a generalization of bipartite graphs to more than two subsets of vertices
1898:
1894:
1753:
algorithms are known for many algorithmic problems on matchings, including
1654:
comes from the fact that a graph is bipartite if and only if it has no odd
1503:
1397:
1249:
830:
A graph is bipartite if and only if every edge belongs to an odd number of
787:
783:
648:
87:
3046:; Smith, Kaleigh; Vetta, Adrian (2004), "Finding odd cycle transversals",
3021:
2316:(2010), "Combinatorics and geometry of finite and infinite squaregraphs",
1769:
for maximum cardinality matching work correctly only on bipartite inputs.
2379:
2016:
1911:
1612:
1448:
769:
660:
641:
616:
536:
83:
50:
1749:
in a graph is a subset of its edges, no two of which share an endpoint.
3209:
3012:
Proceedings of the 10th ACM Symposium on Theory of
Computing (STOC '78)
2646:, Graduate Texts in Mathematics, vol. 184, Springer, p. 165,
1966:
1930:
1378:
1303:
887:
656:
2967:
2341:
3389:
2698:
2083:
Asratian, Armen S.; Denley, Tristan M. J.; Häggkvist, Roland (1998),
1918:
1615:
791:
3171:
2043:
772:, formed from complete bipartite graphs by removing the edges of a
615:
Another example where bipartite graphs appear naturally is in the (
2953:(2009), "Testing bipartiteness of geometric intersection graphs",
2332:
1472:
breadth-first search forest connecting its two endpoints to their
1850:
where an edge connects each job-seeker with each suitable job. A
823:
A graph is bipartite if and only if it is 2-colorable, (i.e. its
808:
Bipartite graphs may be characterized in several different ways:
2830:; Miller, Zevi (1980), "Bigraphs versus digraphs via matrices",
2666:
1642:
would cause the resulting graph to be bipartite. The problem is
1054:{\displaystyle \sum _{v\in V}\deg v=\sum _{u\in U}\deg u=|E|\,.}
768:
edges. Closely related to the complete bipartite graphs are the
3369:
3187:, Application 12.1 Bipartite Personnel Assignment, pp. 463–464.
790:
are bipartite. In these graphs, the vertices may be labeled by
2374:
1201:
875:
the minimum vertex cover is equal to the number of vertices.
655:
all have even length is bipartite. Special cases of this are
447:
denoting the edges of the graph. If a bipartite graph is not
3248:
Error
Correction Coding: Mathematical Methods and Algorithms
934:
For a vertex, the number of adjacent vertices is called the
3199:"Are Medical Students Meeting Their (Best Possible) Match?"
1907:
451:, it may have more than one bipartition; in this case, the
3090:
2003:, a generalization of bipartite graphs in which every two
1757:(finding a matching that uses as many edges as possible),
387:
to denote a bipartite graph whose partition has the parts
2857:. Brualdi et al. credit the idea for this equivalence to
2417:. See especially Chapter 5, "Partial Cubes", pp. 127–181.
2221:
1862:
applies graph matching methods to solve this problem for
296:
of the graph with two colors: if one colors all nodes in
3378:
3370:
Information System on Graph
Classes and their Inclusions
3009:(1978), "Node-and edge-deletion NP-complete problems",
2789:
2426:
2362:
2116:
2082:
3158:
algorithm for maximum matchings in bipartite graphs",
1679:
907:
using a number of colors equal to its maximum degree.
3284:
Cassandras, Christos G.; Lafortune, Stephane (2007),
2748:
Lecture notes: Introduction to Graph Theory, Math 345
2311:
1818:
1798:
1778:
1554:
1516:
1489:
1406:
1313:
1258:
1216:
1117:
1090:
1070:
977:
944:
845:
691:
573:
545:
495:
457:
433:
413:
393:
349:
322:
302:
278:
258:
227:
207:
187:
167:
139:
119:
1467:
Alternatively, a similar procedure may be used with
3283:
3121:
2825:
3184:
3134:
3118:
3084:
2999:
2084:
1842:
1804:
1784:
1715:
1578:
1540:
1495:
1418:
1337:
1290:
1240:
1177:
1096:
1076:
1053:
956:
721:
579:
551:
527:
481:
439:
419:
399:
379:
328:
308:
284:
264:
233:
213:
193:
173:
145:
125:
3232:
2858:
2204:Social Network Analysis: Methods and Applications
3404:
3398:Bipartite graphs in systems biology and medicine
2915:(3rd ed.), Addison Wesley, pp. 109–111
2801:
2616:, Courier Dover Publications, pp. 189–190,
2446:
2433:. For infinite graphs, this result requires the
2007:between the same two points have the same parity
1885:Bipartite graphs are extensively used in modern
1792:of people are all seeking jobs from among a set
3036:
2926:
2143:(3rd ed.), Cengage Learning, p. 363,
2035:
3042:
2602:
2197:
2163:
1548:, even though the graph itself may have up to
644:with an even number of vertices are bipartite.
630:More abstract examples include the following:
2636:
2450:Digraphs: Theory, Algorithms and Applications
3146:
2913:Algorithms in Java, Part 5: Graph Algorithms
2682:(2006), "The strong perfect graph theorem",
2552:
2447:Bang-Jensen, Jørgen; Gutin, Gregory (2001),
1104:. For example, the complete bipartite graph
2575:
2410:
2227:
2133:
1731:is the number of edges in the input graph.
1345:may be used to model a hypergraph in which
1202:Relation to hypergraphs and directed graphs
44:Example of a bipartite graph without cycles
3005:
1880:
1357:contains an edge from a hypergraph vertex
1349:is the set of vertices of the hypergraph,
878:Another class of related results concerns
3104:
3059:
3020:
2966:
2907:
2876:
2863:(1958), "Coverings of bipartite graphs",
2707:
2697:
2331:
2248:
2112:
2110:
2108:
1047:
535:, that is, if the two subsets have equal
3310:
3196:
2949:
2576:Gross, Jonathan L.; Yellen, Jay (2005),
2233:Invitation to Fixed Parameter Algorithms
1975:, a class of matroids that includes the
1772:As a simple example, suppose that a set
1599:
1589:
1442:
898:size is also two) but perfection of the
837:A graph is bipartite if and only if the
69:
49:
3290:(2nd ed.), Springer, p. 224,
3093:Journal of Computer and System Sciences
2790:Asratian, Denley & Häggkvist (1998)
2770:(2nd ed.), Elsevier, p. 281,
2489:
2427:Asratian, Denley & Häggkvist (1998)
2363:Asratian, Denley & Häggkvist (1998)
2117:Asratian, Denley & Häggkvist (1998)
2087:Bipartite Graphs and their Applications
2041:
1965:, a generalization of bipartiteness to
16:Graph divided into two independent sets
3405:
3287:Introduction to Discrete Event Systems
3251:, John Wiley & Sons, p. 638,
2760:
2456:(1st ed.), Springer, p. 25,
2273:
2254:
2105:
3379:
2525:
2283:, Springer-Verlag, pp. 136–137,
2129:
2127:
2125:
1727:is the number of edges to delete and
1716:{\textstyle O\left(2^{k}m^{2}\right)}
1634:, whether there exists a set of
3271:
3244:
2767:Combinatorial Problems and Exercises
2319:SIAM Journal on Discrete Mathematics
2140:Mathematics: A Discrete Introduction
608:, a type of bipartite graph used in
1906:used for probabilistic decoding of
1579:{\displaystyle O\left(n^{2}\right)}
1178:{\displaystyle (5,5,5),(3,3,3,3,3)}
803:
13:
3317:Configurations of Points and Lines
3185:Ahuja, Magnanti & Orlin (1993)
3135:Ahuja, Magnanti & Orlin (1993)
2122:
1860:National Resident Matching Program
968:for a bipartite graph states that
846:KĹ‘nig's theorem and perfect graphs
14:
3434:
3345:
3123:, Prentice Hall, pp. 461–509
2738:
2579:Graph Theory and Its Applications
1618:problem that asks, given a graph
850:In bipartite graphs, the size of
812:An undirected graph is bipartite
2938:, Addison Wesley, pp. 94–97
2298:containing a false proof of the
1875:Dulmage–Mendelsohn decomposition
916:forbidden graph characterization
34:
23:
3322:Graduate Studies in Mathematics
3304:
3277:
3265:
3238:
3233:Dulmage & Mendelsohn (1958)
3226:
3190:
3178:
3140:
3128:
3112:
2943:
2920:
2901:
2865:Canadian Journal of Mathematics
2819:
2795:
2783:
2754:
2732:
2660:
2630:
2596:
2569:
2546:
2519:
2483:
2473:from the original on 2023-01-02
2440:
2420:
2404:
2368:
2356:
2305:
2066:from the original on 2011-04-09
2955:ACM Transactions on Algorithms
2613:A First Course in Graph Theory
2556:(1931), "Gráfok és mátrixok",
2280:The Mathematical Coloring Book
2267:
2191:
2157:
2076:
1837:
1819:
1535:
1520:
1506:or other simple shapes in the
1353:is the set of hyperedges, and
1332:
1314:
1284:
1276:
1268:
1260:
1235:
1217:
1172:
1142:
1136:
1118:
1043:
1035:
886:of every bipartite graph, the
716:
698:
521:
513:
505:
497:
476:
458:
374:
356:
1:
3326:American Mathematical Society
3197:Robinson, Sara (April 2003),
2050:Graduate Texts in Mathematics
2029:
1437:
1291:{\displaystyle |U|\times |V|}
1195:bipartite realization problem
938:of the vertex and is denoted
882:: every bipartite graph, the
798:
2558:Matematikai Ă©s Fizikai Lapok
2506:10.1016/0012-365X(90)90380-Z
2411:Ovchinnikov, Sergei (2011),
2312:Bandelt, H.-J.; Chepoi, V.;
1983:Bipartite network projection
1673:, and can be solved in time
1638:vertices whose removal from
914:, the perfect graphs have a
912:strong perfect graph theorem
854:is equal to the size of the
827:is less than or equal to 2).
7:
3358:Encyclopedia of Mathematics
3048:Operations Research Letters
2809:Encyclopedia of Mathematics
2201:; Faust, Katherine (1994),
1944:
1893:received from the channel.
1734:
1369:is one of the endpoints of
816:it does not contain an odd
594:
10:
3439:
3106:10.1016/j.jcss.2006.02.001
2802:A. A. Sapozhenko (2001) ,
2718:10.4007/annals.2006.164.51
2398:10.1016/j.disc.2003.11.021
1738:
1593:
1541:{\displaystyle O(n\log n)}
841:of the graph is symmetric.
737:are disjoint sets of size
3160:SIAM Journal on Computing
3070:10.1016/j.orl.2003.10.009
2750:, Simon Fraser University
2042:Diestel, Reinard (2005),
1671:fixed-parameter tractable
1644:fixed-parameter tractable
1419:{\displaystyle n\times n}
929:
749:connects every vertex in
722:{\displaystyle G=(U,V,E)}
380:{\displaystyle G=(U,V,E)}
2415:, Universitext, Springer
668:complete bipartite graph
106:can be divided into two
56:complete bipartite graph
3208:(3): 36, archived from
2977:10.1145/1497290.1497291
2833:Journal of Graph Theory
1917:In computer science, a
1889:, especially to decode
1881:Additional applications
1856:Hall's marriage theorem
1843:{\displaystyle (P,J,E)}
1767:Hopcroft–Karp algorithm
1759:maximum weight matching
1741:Matching (graph theory)
1434:of the directed graph.
1338:{\displaystyle (U,V,E)}
1241:{\displaystyle (U,V,E)}
864:maximum independent set
685:is the bipartite graph
610:social network analysis
528:{\displaystyle |U|=|V|}
482:{\displaystyle (U,V,E)}
316:blue, and all nodes in
292:may be thought of as a
241:are usually called the
3245:Moon, Todd K. (2005),
2878:10.4153/CJM-1958-052-0
2846:10.1002/jgt.3190040107
2529:Algebraic Graph Theory
2526:Biggs, Norman (1994),
2174:Chromatic Graph Theory
2135:Scheinerman, Edward R.
1989:Convex bipartite graph
1957:Bipartite double cover
1844:
1806:
1786:
1717:
1605:
1580:
1542:
1497:
1474:lowest common ancestor
1432:bipartite double cover
1420:
1339:
1292:
1242:
1179:
1098:
1078:
1055:
958:
957:{\displaystyle \deg v}
723:
581:
553:
529:
483:
441:
421:
401:
381:
330:
310:
286:
266:
235:
215:
195:
175:
147:
127:
79:
67:
3022:10.1145/800133.804355
2826:Brualdi, Richard A.;
2685:Annals of Mathematics
2011:Quasi-bipartite graph
1941:must be six or more.
1845:
1807:
1787:
1718:
1652:odd cycle transversal
1609:Odd cycle transversal
1603:
1596:Odd cycle transversal
1590:Odd cycle transversal
1581:
1543:
1498:
1443:Testing bipartiteness
1421:
1361:to a hypergraph edge
1340:
1293:
1243:
1210:of a bipartite graph
1180:
1099:
1079:
1056:
959:
753:with all vertices in
724:
678:vertices, denoted by
582:
554:
530:
484:
442:
422:
402:
382:
331:
311:
287:
267:
236:
216:
196:
176:
148:
128:
73:
53:
3423:Parity (mathematics)
3015:, pp. 253–264,
2493:Discrete Mathematics
2385:Discrete Mathematics
2023:Zarankiewicz problem
1963:Bipartite hypergraph
1864:U.S. medical student
1816:
1796:
1776:
1677:
1552:
1514:
1487:
1469:breadth-first search
1404:
1396:vertices can be any
1311:
1256:
1214:
1115:
1111:has degree sequence
1088:
1068:
975:
942:
852:minimum vertex cover
745:, respectively, and
689:
571:
543:
493:
455:
431:
411:
391:
347:
320:
300:
276:
256:
225:
205:
185:
165:
137:
117:
3007:Yannakakis, Mihalis
2643:Modern Graph Theory
1979:of bipartite graphs
1951:Bipartite dimension
1927:projective geometry
1481:intersection graphs
757:. It follows that
606:affiliation network
3381:Weisstein, Eric W.
3353:"Graph, bipartite"
2300:four color theorem
2199:Wasserman, Stanley
1995:Multipartite graph
1868:hospital residency
1840:
1802:
1782:
1713:
1667:edge bipartization
1606:
1576:
1538:
1493:
1457:preorder traversal
1453:depth-first search
1416:
1375:incidence matrices
1335:
1288:
1238:
1208:biadjacency matrix
1175:
1094:
1074:
1051:
1021:
993:
966:degree sum formula
954:
872:minimum edge cover
719:
577:
549:
525:
479:
437:
417:
397:
377:
326:
306:
282:
262:
231:
211:
191:
171:
143:
123:
80:
68:
3385:"Bipartite Graph"
3324:, vol. 103,
3148:Hopcroft, John E.
2909:Sedgewick, Robert
2861:Mendelsohn, N. S.
2668:Chudnovsky, Maria
2342:10.1137/090760301
2290:978-0-387-74640-1
2275:Soifer, Alexander
2242:978-0-19-856607-6
2229:Niedermeier, Rolf
2059:978-3-642-14278-9
1973:Bipartite matroid
1805:{\displaystyle J}
1785:{\displaystyle P}
1496:{\displaystyle n}
1097:{\displaystyle V}
1077:{\displaystyle U}
1006:
978:
910:According to the
894:is two and their
868:isolated vertices
580:{\displaystyle G}
552:{\displaystyle G}
440:{\displaystyle E}
420:{\displaystyle V}
400:{\displaystyle U}
343:One often writes
329:{\displaystyle V}
309:{\displaystyle U}
285:{\displaystyle V}
265:{\displaystyle U}
234:{\displaystyle V}
214:{\displaystyle U}
194:{\displaystyle V}
174:{\displaystyle U}
153:, that is, every
146:{\displaystyle V}
126:{\displaystyle U}
3430:
3418:Bipartite graphs
3394:
3393:
3366:
3340:
3338:
3312:GrĂĽnbaum, Branko
3308:
3302:
3300:
3281:
3275:
3269:
3263:
3261:
3242:
3236:
3230:
3224:
3222:
3221:
3220:
3214:
3203:
3194:
3188:
3182:
3176:
3174:
3152:Karp, Richard M.
3144:
3138:
3132:
3126:
3124:
3116:
3110:
3109:
3108:
3099:(8): 1386–1396,
3088:
3082:
3080:
3063:
3040:
3034:
3033:
3024:
3003:
2997:
2995:
2970:
2947:
2941:
2939:
2936:Algorithm Design
2924:
2918:
2916:
2905:
2899:
2897:
2880:
2859:Dulmage, A. L.;
2856:
2823:
2817:
2816:
2799:
2793:
2787:
2781:
2780:
2758:
2752:
2751:
2745:
2736:
2730:
2728:
2711:
2701:
2664:
2658:
2656:
2634:
2628:
2626:
2600:
2594:
2592:
2573:
2567:
2565:
2550:
2544:
2542:
2523:
2517:
2516:
2487:
2481:
2480:
2479:
2478:
2472:
2455:
2444:
2438:
2424:
2418:
2416:
2413:Graphs and Cubes
2408:
2402:
2400:
2378:; Debowsky, M.;
2372:
2366:
2360:
2354:
2352:
2335:
2326:(4): 1399–1440,
2309:
2303:
2293:
2271:
2265:
2264:
2263:, pp. 65–84
2252:
2246:
2245:
2225:
2219:
2217:
2195:
2189:
2187:
2161:
2155:
2153:
2131:
2120:
2114:
2103:
2101:
2090:
2080:
2074:
2073:
2072:
2071:
2039:
1977:graphic matroids
1866:job-seekers and
1852:perfect matching
1849:
1847:
1846:
1841:
1811:
1809:
1808:
1803:
1791:
1789:
1788:
1783:
1755:maximum matching
1722:
1720:
1719:
1714:
1712:
1708:
1707:
1706:
1697:
1696:
1585:
1583:
1582:
1577:
1575:
1571:
1570:
1547:
1545:
1544:
1539:
1502:
1500:
1499:
1494:
1429:
1425:
1423:
1422:
1417:
1395:
1372:
1368:
1364:
1360:
1356:
1352:
1348:
1344:
1342:
1341:
1336:
1297:
1295:
1294:
1289:
1287:
1279:
1271:
1263:
1247:
1245:
1244:
1239:
1184:
1182:
1181:
1176:
1103:
1101:
1100:
1095:
1083:
1081:
1080:
1075:
1060:
1058:
1057:
1052:
1046:
1038:
1020:
992:
963:
961:
960:
955:
924:induced subgraph
892:chromatic number
870:the size of the
856:maximum matching
825:chromatic number
804:Characterization
780:Hypercube graphs
774:perfect matching
728:
726:
725:
720:
586:
584:
583:
578:
558:
556:
555:
550:
534:
532:
531:
526:
524:
516:
508:
500:
488:
486:
485:
480:
446:
444:
443:
438:
426:
424:
423:
418:
406:
404:
403:
398:
386:
384:
383:
378:
335:
333:
332:
327:
315:
313:
312:
307:
291:
289:
288:
283:
271:
269:
268:
263:
240:
238:
237:
232:
220:
218:
217:
212:
200:
198:
197:
192:
180:
178:
177:
172:
152:
150:
149:
144:
132:
130:
129:
124:
112:independent sets
38:
27:
3438:
3437:
3433:
3432:
3431:
3429:
3428:
3427:
3403:
3402:
3374:bipartite graph
3351:
3348:
3343:
3336:
3309:
3305:
3298:
3282:
3278:
3270:
3266:
3259:
3243:
3239:
3231:
3227:
3218:
3216:
3212:
3201:
3195:
3191:
3183:
3179:
3172:10.1137/0202019
3145:
3141:
3133:
3129:
3117:
3113:
3089:
3085:
3061:10.1.1.112.6357
3041:
3037:
3004:
3000:
2951:Eppstein, David
2948:
2944:
2925:
2921:
2906:
2902:
2824:
2820:
2800:
2796:
2788:
2784:
2778:
2759:
2755:
2743:
2737:
2733:
2709:10.1.1.111.7265
2672:Robertson, Neil
2665:
2661:
2654:
2635:
2631:
2624:
2604:Chartrand, Gary
2601:
2597:
2590:
2574:
2570:
2551:
2547:
2540:
2524:
2520:
2488:
2484:
2476:
2474:
2470:
2464:
2453:
2445:
2441:
2435:axiom of choice
2425:
2421:
2409:
2405:
2373:
2369:
2361:
2357:
2310:
2306:
2291:
2272:
2268:
2261:Spink & Son
2253:
2249:
2243:
2226:
2222:
2215:
2196:
2192:
2185:
2165:Chartrand, Gary
2162:
2158:
2151:
2132:
2123:
2115:
2106:
2099:
2081:
2077:
2069:
2067:
2060:
2040:
2036:
2032:
1947:
1883:
1817:
1814:
1813:
1797:
1794:
1793:
1777:
1774:
1773:
1763:stable marriage
1751:Polynomial time
1743:
1737:
1702:
1698:
1692:
1688:
1687:
1683:
1678:
1675:
1674:
1630:) and a number
1598:
1592:
1566:
1562:
1558:
1553:
1550:
1549:
1515:
1512:
1511:
1508:Euclidean plane
1488:
1485:
1484:
1461:spanning forest
1445:
1440:
1427:
1405:
1402:
1401:
1393:
1390:directed graphs
1370:
1366:
1362:
1358:
1354:
1350:
1346:
1312:
1309:
1308:
1283:
1275:
1267:
1259:
1257:
1254:
1253:
1215:
1212:
1211:
1204:
1116:
1113:
1112:
1110:
1089:
1086:
1085:
1069:
1066:
1065:
1042:
1034:
1010:
982:
976:
973:
972:
943:
940:
939:
932:
860:KĹ‘nig's theorem
848:
806:
801:
762:
690:
687:
686:
683:
599:When modelling
597:
572:
569:
568:
544:
541:
540:
520:
512:
504:
496:
494:
491:
490:
456:
453:
452:
432:
429:
428:
412:
409:
408:
392:
389:
388:
348:
345:
344:
321:
318:
317:
301:
298:
297:
277:
274:
273:
257:
254:
253:
226:
223:
222:
206:
203:
202:
186:
183:
182:
166:
163:
162:
138:
135:
134:
118:
115:
114:
92:bipartite graph
48:
47:
46:
45:
41:
40:
39:
30:
29:
28:
17:
12:
11:
5:
3436:
3426:
3425:
3420:
3415:
3413:Graph families
3401:
3400:
3395:
3376:
3367:
3347:
3346:External links
3344:
3342:
3341:
3334:
3328:, p. 28,
3303:
3296:
3276:
3264:
3257:
3237:
3225:
3189:
3177:
3166:(4): 225–231,
3139:
3127:
3111:
3083:
3054:(4): 299–301,
3035:
2998:
2961:(2): Art. 15,
2942:
2928:Kleinberg, Jon
2919:
2900:
2818:
2794:
2782:
2776:
2762:Lovász, László
2753:
2731:
2659:
2652:
2629:
2622:
2595:
2588:
2568:
2545:
2538:
2518:
2500:(2): 217–220,
2482:
2462:
2439:
2419:
2403:
2392:(1–3): 37–43,
2376:Archdeacon, D.
2367:
2355:
2304:
2289:
2266:
2247:
2241:
2220:
2213:
2190:
2183:
2156:
2149:
2121:
2104:
2097:
2075:
2058:
2033:
2031:
2028:
2027:
2026:
2020:
2014:
2008:
1998:
1992:
1986:
1980:
1970:
1960:
1954:
1946:
1943:
1904:belief network
1882:
1879:
1839:
1836:
1833:
1830:
1827:
1824:
1821:
1801:
1781:
1739:Main article:
1736:
1733:
1711:
1705:
1701:
1695:
1691:
1686:
1682:
1594:Main article:
1591:
1588:
1574:
1569:
1565:
1561:
1557:
1537:
1534:
1531:
1528:
1525:
1522:
1519:
1492:
1444:
1441:
1439:
1436:
1415:
1412:
1409:
1334:
1331:
1328:
1325:
1322:
1319:
1316:
1286:
1282:
1278:
1274:
1270:
1266:
1262:
1237:
1234:
1231:
1228:
1225:
1222:
1219:
1203:
1200:
1174:
1171:
1168:
1165:
1162:
1159:
1156:
1153:
1150:
1147:
1144:
1141:
1138:
1135:
1132:
1129:
1126:
1123:
1120:
1108:
1093:
1073:
1062:
1061:
1050:
1045:
1041:
1037:
1033:
1030:
1027:
1024:
1019:
1016:
1013:
1009:
1005:
1002:
999:
996:
991:
988:
985:
981:
953:
950:
947:
931:
928:
896:maximum clique
880:perfect graphs
847:
844:
843:
842:
835:
828:
821:
814:if and only if
805:
802:
800:
797:
796:
795:
777:
760:
718:
715:
712:
709:
706:
703:
700:
697:
694:
681:
664:
645:
639:
621:dominating set
596:
593:
576:
548:
523:
519:
515:
511:
507:
503:
499:
478:
475:
472:
469:
466:
463:
460:
436:
416:
396:
376:
373:
370:
367:
364:
361:
358:
355:
352:
325:
305:
281:
261:
230:
210:
201:. Vertex sets
190:
170:
142:
122:
43:
42:
33:
32:
31:
22:
21:
20:
19:
18:
15:
9:
6:
4:
3:
2:
3435:
3424:
3421:
3419:
3416:
3414:
3411:
3410:
3408:
3399:
3396:
3392:
3391:
3386:
3382:
3377:
3375:
3371:
3368:
3364:
3360:
3359:
3354:
3350:
3349:
3337:
3335:9780821843086
3331:
3327:
3323:
3319:
3318:
3313:
3307:
3299:
3297:9780387333328
3293:
3289:
3288:
3280:
3273:
3268:
3260:
3258:9780471648000
3254:
3250:
3249:
3241:
3234:
3229:
3215:on 2016-11-18
3211:
3207:
3200:
3193:
3186:
3181:
3173:
3169:
3165:
3161:
3157:
3153:
3149:
3143:
3136:
3131:
3122:
3115:
3107:
3102:
3098:
3094:
3087:
3079:
3075:
3071:
3067:
3062:
3057:
3053:
3049:
3045:
3039:
3032:
3028:
3023:
3018:
3014:
3013:
3008:
3002:
2994:
2990:
2986:
2982:
2978:
2974:
2969:
2968:cs.CG/0307023
2964:
2960:
2956:
2952:
2946:
2937:
2933:
2929:
2923:
2914:
2910:
2904:
2896:
2892:
2888:
2884:
2879:
2874:
2870:
2866:
2862:
2855:
2851:
2847:
2843:
2839:
2835:
2834:
2829:
2828:Harary, Frank
2822:
2815:
2811:
2810:
2805:
2798:
2791:
2786:
2779:
2777:9780080933092
2773:
2769:
2768:
2763:
2757:
2749:
2742:
2739:DeVos, Matt,
2735:
2727:
2723:
2719:
2715:
2710:
2705:
2700:
2695:
2692:(1): 51–229,
2691:
2687:
2686:
2681:
2680:Thomas, Robin
2677:
2676:Seymour, Paul
2673:
2669:
2663:
2655:
2653:9780387984889
2649:
2645:
2644:
2639:
2638:Béla Bollobás
2633:
2625:
2623:9780486483689
2619:
2615:
2614:
2609:
2605:
2599:
2591:
2589:9781584885054
2585:
2581:
2580:
2572:
2563:
2559:
2555:
2549:
2541:
2539:9780521458979
2535:
2531:
2530:
2522:
2515:
2511:
2507:
2503:
2499:
2495:
2494:
2486:
2469:
2465:
2463:9781852332686
2459:
2452:
2451:
2443:
2436:
2432:
2428:
2423:
2414:
2407:
2399:
2395:
2391:
2387:
2386:
2381:
2377:
2371:
2364:
2359:
2351:
2347:
2343:
2339:
2334:
2329:
2325:
2321:
2320:
2315:
2308:
2301:
2297:
2292:
2286:
2282:
2281:
2276:
2270:
2262:
2258:
2251:
2244:
2238:
2234:
2230:
2224:
2216:
2214:9780521387071
2210:
2206:
2205:
2200:
2194:
2186:
2184:9781584888000
2180:
2176:
2175:
2170:
2166:
2160:
2152:
2150:9780840049421
2146:
2142:
2141:
2136:
2130:
2128:
2126:
2118:
2113:
2111:
2109:
2100:
2098:9780521593458
2094:
2089:
2088:
2079:
2065:
2061:
2055:
2051:
2047:
2046:
2038:
2034:
2024:
2021:
2018:
2015:
2012:
2009:
2006:
2005:induced paths
2002:
1999:
1996:
1993:
1990:
1987:
1984:
1981:
1978:
1974:
1971:
1968:
1964:
1961:
1958:
1955:
1952:
1949:
1948:
1942:
1940:
1936:
1935:configuration
1932:
1928:
1923:
1920:
1915:
1913:
1909:
1905:
1900:
1899:Tanner graphs
1896:
1895:Factor graphs
1892:
1888:
1887:coding theory
1878:
1876:
1871:
1869:
1865:
1861:
1857:
1853:
1834:
1831:
1828:
1825:
1822:
1799:
1779:
1770:
1768:
1764:
1760:
1756:
1752:
1748:
1742:
1732:
1730:
1726:
1709:
1703:
1699:
1693:
1689:
1684:
1680:
1672:
1668:
1663:
1661:
1657:
1653:
1649:
1645:
1641:
1637:
1633:
1629:
1625:
1621:
1617:
1614:
1610:
1602:
1597:
1587:
1572:
1567:
1563:
1559:
1555:
1532:
1529:
1526:
1523:
1517:
1509:
1505:
1504:line segments
1490:
1482:
1477:
1475:
1470:
1465:
1462:
1458:
1454:
1450:
1435:
1433:
1413:
1410:
1407:
1399:
1391:
1386:
1384:
1380:
1376:
1365:exactly when
1329:
1326:
1323:
1320:
1317:
1305:
1300:
1280:
1272:
1264:
1251:
1232:
1229:
1226:
1223:
1220:
1209:
1199:
1196:
1191:
1188:
1169:
1166:
1163:
1160:
1157:
1154:
1151:
1148:
1145:
1139:
1133:
1130:
1127:
1124:
1121:
1107:
1091:
1071:
1048:
1039:
1031:
1028:
1025:
1022:
1017:
1014:
1011:
1007:
1003:
1000:
997:
994:
989:
986:
983:
979:
971:
970:
969:
967:
951:
948:
945:
937:
927:
925:
921:
917:
913:
908:
906:
905:edge coloring
901:
897:
893:
889:
885:
881:
876:
873:
869:
865:
861:
857:
853:
840:
836:
833:
829:
826:
822:
819:
815:
811:
810:
809:
793:
789:
788:median graphs
785:
784:partial cubes
781:
778:
775:
771:
767:
763:
756:
752:
748:
744:
740:
736:
732:
713:
710:
707:
704:
701:
695:
692:
684:
677:
673:
669:
665:
662:
658:
654:
650:
646:
643:
640:
638:is bipartite.
637:
633:
632:
631:
628:
624:
622:
618:
613:
611:
607:
602:
592:
590:
574:
566:
562:
546:
538:
517:
509:
501:
473:
470:
467:
464:
461:
450:
434:
414:
394:
371:
368:
365:
362:
359:
353:
350:
341:
339:
323:
303:
295:
279:
259:
252:The two sets
250:
248:
244:
228:
208:
188:
168:
160:
156:
140:
120:
113:
109:
105:
101:
97:
93:
89:
85:
78:is bipartite.
77:
76:Heawood graph
72:
65:
61:
57:
52:
37:
26:
3388:
3356:
3316:
3306:
3286:
3279:
3267:
3247:
3240:
3228:
3217:, retrieved
3210:the original
3205:
3192:
3180:
3163:
3159:
3155:
3154:(1973), "An
3142:
3130:
3120:
3114:
3096:
3092:
3086:
3051:
3047:
3038:
3011:
3001:
2958:
2954:
2945:
2935:
2922:
2912:
2903:
2868:
2864:
2840:(1): 51–73,
2837:
2831:
2821:
2807:
2804:"Hypergraph"
2797:
2785:
2766:
2756:
2747:
2734:
2699:math/0212070
2689:
2683:
2662:
2642:
2632:
2612:
2598:
2578:
2571:
2561:
2557:
2554:KĹ‘nig, DĂ©nes
2548:
2528:
2521:
2497:
2491:
2485:
2475:, retrieved
2449:
2442:
2422:
2412:
2406:
2389:
2383:
2370:
2358:
2323:
2317:
2314:Eppstein, D.
2307:
2296:Alfred Kempe
2279:
2269:
2256:
2250:
2232:
2223:
2203:
2193:
2173:
2159:
2139:
2086:
2078:
2068:, retrieved
2052:, Springer,
2045:Graph Theory
2044:
2037:
2001:Parity graph
1924:
1916:
1884:
1872:
1771:
1744:
1728:
1724:
1666:
1664:
1651:
1647:
1639:
1635:
1631:
1627:
1623:
1619:
1607:
1478:
1466:
1446:
1398:(0,1) matrix
1387:
1301:
1250:(0,1) matrix
1205:
1192:
1105:
1063:
933:
909:
877:
849:
807:
770:crown graphs
765:
758:
754:
750:
746:
742:
738:
734:
730:
679:
675:
671:
661:squaregraphs
649:planar graph
642:Cycle graphs
629:
625:
614:
605:
598:
560:
559:is called a
342:
251:
242:
95:
91:
88:graph theory
84:mathematical
81:
63:
59:
3272:Moon (2005)
3044:Reed, Bruce
2932:Tardos, Éva
2871:: 517–534,
2741:"Matchings"
2608:Zhang, Ping
2431:DĂ©nes KĹ‘nig
2169:Zhang, Ping
2017:Split graph
1967:hypergraphs
1931:Levi graphs
1912:turbo codes
1660:transversal
1650:. The name
1616:algorithmic
1613:NP-complete
1449:linear time
900:complements
657:grid graphs
617:NP-complete
537:cardinality
157:connects a
3407:Categories
3219:2012-08-27
2477:2023-01-02
2380:Dinitz, J.
2070:2012-02-27
2030:References
1438:Algorithms
1379:multigraph
1304:hypergraph
1187:Isomorphic
920:complement
888:line graph
884:complement
858:; this is
799:Properties
792:bitvectors
587:is called
181:to one in
3390:MathWorld
3363:EMS Press
3274:, p. 686.
3206:SIAM News
3056:CiteSeerX
2895:123363425
2814:EMS Press
2726:119151552
2704:CiteSeerX
2564:: 116–119
2333:0905.4537
1919:Petri net
1891:codewords
1530:
1411:×
1273:×
1026:
1015:∈
1008:∑
998:
987:∈
980:∑
949:
601:relations
589:biregular
449:connected
86:field of
3314:(2009),
2934:(2006),
2911:(2004),
2792:, p. 17.
2764:(2014),
2640:(1998),
2610:(2012),
2468:archived
2365:, p. 11.
2350:10788524
2277:(2008),
2231:(2006),
2171:(2008),
2137:(2012),
2064:archived
1945:See also
1902:related
1747:matching
1735:Matching
1723:, where
1479:For the
1451:, using
1400:of size
1252:of size
839:spectrum
729:, where
595:Examples
561:balanced
338:triangle
294:coloring
108:disjoint
104:vertices
62:= 5 and
3365:, 2001
3078:2057781
2985:2561751
2887:0097069
2854:0558453
2514:1071664
2119:, p. 7.
1586:edges.
567:, then
539:, then
427:, with
98:) is a
96:bigraph
82:In the
3332:
3294:
3255:
3076:
3058:
3031:363248
3029:
2991:
2983:
2893:
2885:
2852:
2774:
2724:
2706:
2650:
2620:
2586:
2536:
2512:
2460:
2348:
2287:
2239:
2211:
2181:
2147:
2095:
2056:
1870:jobs.
1761:, and
1656:cycles
1611:is an
1383:degree
964:. The
936:degree
930:Degree
922:as an
786:, and
651:whose
647:Every
634:Every
565:degree
247:cycles
159:vertex
102:whose
3213:(PDF)
3202:(PDF)
3027:S2CID
2993:60496
2989:S2CID
2963:arXiv
2891:S2CID
2744:(PDF)
2722:S2CID
2694:arXiv
2471:(PDF)
2454:(PDF)
2346:S2CID
2328:arXiv
1939:girth
1385:two.
1248:is a
832:bonds
818:cycle
653:faces
243:parts
100:graph
58:with
3330:ISBN
3292:ISBN
3253:ISBN
2772:ISBN
2648:ISBN
2618:ISBN
2584:ISBN
2534:ISBN
2458:ISBN
2285:ISBN
2237:ISBN
2209:ISBN
2179:ISBN
2145:ISBN
2093:ISBN
2054:ISBN
1910:and
1908:LDPC
1897:and
1873:The
1665:The
1206:The
1193:The
1084:and
764:has
741:and
733:and
674:and
666:The
659:and
636:tree
407:and
272:and
221:and
155:edge
133:and
110:and
94:(or
90:, a
74:The
3168:doi
3101:doi
3066:doi
3017:doi
2973:doi
2873:doi
2842:doi
2714:doi
2690:164
2502:doi
2394:doi
2390:284
2338:doi
1925:In
1622:= (
1527:log
1483:of
1109:3,5
1023:deg
995:deg
946:deg
761:m,n
682:n,m
670:on
161:in
66:= 3
3409::
3387:,
3383:,
3372::
3361:,
3355:,
3320:,
3204:,
3162:,
3150:;
3097:72
3095:,
3074:MR
3072:,
3064:,
3052:32
3050:,
3025:,
2987:,
2981:MR
2979:,
2971:,
2957:,
2930:;
2889:,
2883:MR
2881:,
2869:10
2867:,
2850:MR
2848:,
2836:,
2812:,
2806:,
2746:,
2720:,
2712:,
2702:,
2688:,
2678:;
2674:;
2670:;
2606:;
2562:38
2560:,
2510:MR
2508:,
2498:84
2496:,
2466:,
2388:,
2344:,
2336:,
2324:24
2322:,
2259:,
2167:;
2124:^
2107:^
2062:,
2048:,
1929:,
1914:.
1745:A
1302:A
1185:.
782:,
766:mn
612:.
591:.
249:.
54:A
3339:.
3301:.
3262:.
3235:.
3223:.
3175:.
3170::
3164:2
3156:n
3125:.
3103::
3081:.
3068::
3019::
2996:.
2975::
2965::
2959:5
2940:.
2917:.
2898:.
2875::
2844::
2838:4
2729:.
2716::
2696::
2657:.
2627:.
2593:.
2566:.
2543:.
2504::
2437:.
2401:.
2396::
2353:.
2340::
2330::
2302:.
2218:.
2188:.
2154:.
2102:.
1969:.
1838:)
1835:E
1832:,
1829:J
1826:,
1823:P
1820:(
1800:J
1780:P
1729:m
1725:k
1710:)
1704:2
1700:m
1694:k
1690:2
1685:(
1681:O
1648:k
1640:G
1636:k
1632:k
1628:E
1626:,
1624:V
1620:G
1573:)
1568:2
1564:n
1560:(
1556:O
1536:)
1533:n
1524:n
1521:(
1518:O
1491:n
1428:n
1414:n
1408:n
1394:n
1371:e
1367:v
1363:e
1359:v
1355:E
1351:V
1347:U
1333:)
1330:E
1327:,
1324:V
1321:,
1318:U
1315:(
1285:|
1281:V
1277:|
1269:|
1265:U
1261:|
1236:)
1233:E
1230:,
1227:V
1224:,
1221:U
1218:(
1173:)
1170:3
1167:,
1164:3
1161:,
1158:3
1155:,
1152:3
1149:,
1146:3
1143:(
1140:,
1137:)
1134:5
1131:,
1128:5
1125:,
1122:5
1119:(
1106:K
1092:V
1072:U
1049:.
1044:|
1040:E
1036:|
1032:=
1029:u
1018:U
1012:u
1004:=
1001:v
990:V
984:v
952:v
820:.
776:.
759:K
755:V
751:U
747:E
743:n
739:m
735:V
731:U
717:)
714:E
711:,
708:V
705:,
702:U
699:(
696:=
693:G
680:K
676:n
672:m
575:G
547:G
522:|
518:V
514:|
510:=
506:|
502:U
498:|
477:)
474:E
471:,
468:V
465:,
462:U
459:(
435:E
415:V
395:U
375:)
372:E
369:,
366:V
363:,
360:U
357:(
354:=
351:G
324:V
304:U
280:V
260:U
229:V
209:U
189:V
169:U
141:V
121:U
64:n
60:m
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
.svg)