Premium
Monochromatic cycle partitions of edge‐colored graphs
Author(s) -
Sárközy Gábor N.
Publication year - 2011
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.20492
Subject(s) - combinatorics , monochromatic color , conjecture , mathematics , independence number , disjoint sets , vertex (graph theory) , partition (number theory) , discrete mathematics , graph , physics , optics
Abstract In this article we study the monochromatic cycle partition problem for non‐complete graphs. We consider graphs with a given independence number α( G ) = α. Generalizing a classical conjecture of Erdös, Gyárfás and Pyber, we conjecture that if we r ‐color the edges of a graph G with α( G ) = α, then the vertex set of G can be partitioned into at most α r vertex disjoint monochromatic cycles. In the direction of this conjecture we show that under these conditions the vertex set of G can be partitioned into at most 25(α r ) 2 log(α r ) vertex disjoint monochromatic cycles. © 2010 Wiley Periodicals, Inc. J Graph Theory 66: 57–64, 2010