Edge-disjoint odd cycles in graphs with small chromatic numbers
type: Item
instance of: scholarly article
title: Edge-disjoint odd cycles in graphs with small chromatic numbers
zbMATH Open document ID: 0923.05034
author: Bruce Reed
author: C. Berge
publication date: 1999-07-12T00:00:00Z
full work available at URL: http://www.numdam.org/item
full work available at URL: https://eudml.org/doc/75362
review text: 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\).
Mathematics Subject Classification ID: 05C38
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 91A24
Mathematics Subject Classification ID: 91A43
zbMATH DE Number: 1314944
zbMATH Keywords: graph
zbMATH Keywords: games
zbMATH Keywords: positional game
zbMATH Keywords: monochromatic odd cycle
zbMATH Keywords: winning strategy
zbMATH Keywords: chromatic number
zbMATH Keywords: edge-disjoint odd cycles
reviewed by: Arthur T. White
Wikidata QID: Q114013476
MaRDI profile type: Publication
OpenAlex ID: W2048584632
cites work: Q3993087
cites work: On the optimal transversals of the odd cycles
cites work: Optimal packings of edge-disjoint odd cycles
cites work: Hajos' graph-coloring conjecture: Variations and counterexamples
cites work: Une classe d'hypergraphes bichromatiques
cites work: Normal hypergraphs and the perfect graph conjecture
cites work: Q4352948
cites work: On the presence of disjoint subgraphs of a specified type
cites work: Q4857375
DOI: 10.5802/AIF.1691
published in: Annales de l’institut Fourier
description: scientific article; zbMATH DE number 1314944