![](/files/happy5.png)
Pach, János
Odd-cycle transversal in triangle-free graphs ★★
Author(s): Erdos; Faudree; Pach; Spencer
Conjecture If
is a simple triangle-free graph, then there is a set of at most
edges whose deletion destroys every odd cycle.
![$ G $](/files/tex/b8e7ad0330f925492bf468b5c379baec88cf1b3d.png)
![$ n^2/25 $](/files/tex/0db5eaf8ff84c2da58a206455442346f6fa11c19.png)
Keywords:
Are different notions of the crossing number the same? ★★★
Problem Does the following equality hold for every graph
?
![$ G $](/files/tex/b8e7ad0330f925492bf468b5c379baec88cf1b3d.png)
![\[ \text{pair-cr}(G) = \text{cr}(G) \]](/files/tex/8cece1e00bb0e9fc122e0a5cad0dab2681cf33a4.png)
The crossing number of a graph
is the minimum number of edge crossings in any drawing of
in the plane. In the pairwise crossing number
, we minimize the number of pairs of edges that cross.
Keywords: crossing number; pair-crossing number
![Syndicate content Syndicate content](/misc/feed.png)