![](/files/happy5.png)
Berge, Claude
Linial-Berge path partition duality ★★★
Conjecture The minimum
-norm of a path partition on a directed graph
is no more than the maximal size of an induced
-colorable subgraph.
![$ k $](/files/tex/c450c3185f7285cfa0b88d3a903c54f7df601201.png)
![$ D $](/files/tex/b8653a25aff72e3dacd3642492c24c2241f0058c.png)
![$ k $](/files/tex/c450c3185f7285cfa0b88d3a903c54f7df601201.png)
Keywords: coloring; directed path; partition
The Berge-Fulkerson conjecture ★★★★
Conjecture If
is a bridgeless cubic graph, then there exist 6 perfect matchings
of
with the property that every edge of
is contained in exactly two of
.
![$ G $](/files/tex/b8e7ad0330f925492bf468b5c379baec88cf1b3d.png)
![$ M_1,\ldots,M_6 $](/files/tex/8ab42e6cd40fd3556882bbb8216d0b8e14f3bf3e.png)
![$ G $](/files/tex/b8e7ad0330f925492bf468b5c379baec88cf1b3d.png)
![$ G $](/files/tex/b8e7ad0330f925492bf468b5c379baec88cf1b3d.png)
![$ M_1,\ldots,M_6 $](/files/tex/8ab42e6cd40fd3556882bbb8216d0b8e14f3bf3e.png)
Keywords: cubic; perfect matching
![Syndicate content Syndicate content](/misc/feed.png)