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

From MaRDI portal
Added link to MaRDI item.
ReferenceBot (talk | contribs)
Changed an Item
 
(5 intermediate revisions by 4 users not shown)
Property / author
 
Property / author: Bruce A. Reed / rank
Normal rank
 
Property / reviewed by
 
Property / reviewed by: Arthur T. White / rank
Normal rank
 
Property / author
 
Property / author: Bruce A. Reed / rank
 
Normal rank
Property / reviewed by
 
Property / reviewed by: Arthur T. White / rank
 
Normal rank
Property / Wikidata QID
 
Property / Wikidata QID: Q114013476 / rank
 
Normal rank
Property / MaRDI profile type
 
Property / MaRDI profile type: MaRDI publication profile / rank
 
Normal rank
Property / OpenAlex ID
 
Property / OpenAlex ID: W2048584632 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q3993087 / rank
 
Normal rank
Property / cites work
 
Property / cites work: On the optimal transversals of the odd cycles / rank
 
Normal rank
Property / cites work
 
Property / cites work: Optimal packings of edge-disjoint odd cycles / rank
 
Normal rank
Property / cites work
 
Property / cites work: Hajos' graph-coloring conjecture: Variations and counterexamples / rank
 
Normal rank
Property / cites work
 
Property / cites work: Une classe d'hypergraphes bichromatiques / rank
 
Normal rank
Property / cites work
 
Property / cites work: Normal hypergraphs and the perfect graph conjecture / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q4352948 / rank
 
Normal rank
Property / cites work
 
Property / cites work: On the presence of disjoint subgraphs of a specified type / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q4857375 / rank
 
Normal rank

Latest revision as of 20:20, 28 May 2024

scientific article
Language Label Description Also known as
English
Edge-disjoint odd cycles in graphs with small chromatic numbers
scientific article

    Statements

    Edge-disjoint odd cycles in graphs with small chromatic numbers (English)
    0 references
    0 references
    0 references
    12 July 1999
    0 references
    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\).
    0 references
    graph
    0 references
    games
    0 references
    positional game
    0 references
    monochromatic odd cycle
    0 references
    winning strategy
    0 references
    chromatic number
    0 references
    edge-disjoint odd cycles
    0 references

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references