Monochromatic Graph Decompositions Inspired by Anti-Ramsey Theory and Parity Constraints

Yair Caro and Zsolt Tuza ()
Additional contact information
Yair Caro: Department of Mathematics, University of Haifa-Oranim, Tivon 36006, Israel
Zsolt Tuza: HUN-REN Alfréd Rényi Institute of Mathematics, 1053 Budapest, Hungary

Mathematics, 2024, vol. 12, issue 23, 1-33

Abstract: We open here many new tracks of research in anti-Ramsey Theory, considering edge-coloring problems inspired by rainbow coloring and further by odd colorings and conflict-free colorings. Let G be a graph and F any given family of graphs. For every integer n ≥ | G | , let f ( n , G | F ) denote the smallest integer k such that any edge coloring of K n with at least k colors forces a copy of G in which each color class induces a member of F . Observe that in anti-Ramsey problems, each color class is a single edge, i.e., F = { K 2 } . Among the many results introduced in this paper, we mention the following. (1) For every graph G , there exists a constant c = c ( G ) such that in any edge coloring of K n with at least c n colors there is a copy of G in which every vertex v is incident with an edge whose color appears only once among all edges incident with v . (2) In sharp contrast to the above result we prove that if F is the class of all odd graphs (having vertices with odd degrees only) then f ( n , K k | F ) = ( 1 + o ( 1 ) ) ex ( n , K ⌈ k / 2 ⌉ ) , which is quadratic for k ≥ 5 . (3) We exactly determine f ( n , G | F ) for small graphs when F belongs to several families representing various odd/even coloring constraints.

Keywords: anti-Ramsey; odd coloring; conflict-free coloring; parity colorings (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2024
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/12/23/3665/pdf (application/pdf)
https://www.mdpi.com/2227-7390/12/23/3665/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:12:y:2024:i:23:p:3665-:d:1527301

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().