Edge-disjoint odd cycles in graphs with small chromatic numbers (Q1296141): Difference between revisions

Two players, Red and Blue, play a positional game alternately by coloring with their color an edge in a graph \(G\). The first one who achieves a monochromatic odd cycle wins and his opponent loses; if no monochromatic odd cycle is produced, the outcome is a draw. The authors show that there is a winning strategy for the first player, if \(G\) has chromatic number \(>4\). The edge-transversal number \(\tau_e(G)\) is the least number of edges to remove from \(G\) in order to destroy all odd cycles. The edge-packing number \(\upsilon_e(G)\) is the maximum number of pairwise edge-disjoint odd cycles; if \(G\) has no odd cycles, set \(\upsilon_e(G)= 0\). The authors show that if \(\tau_e(G')= \upsilon_e(G')\) for every partial graph \(G'\) of \(G\), then \(G\) has chromatic number \(<4\).