Rainbow saturation

DOI10.1007/S00373-022-02566-ZzbMATH Open1498.05092OpenAlexW4297475898MaRDI QIDQ2084787FDOQ2084787

Authors Yanyan Li

Publication date 13 October 2022

Published in Graphs and Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2003.13200

zbMATH Keywords

extremal graph theorysaturationedge coloring

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Coloring of graphs and hypergraphs (05C15) Paths and cycles (05C38)

Abstract: We introduce a notion of rainbow saturation and the corresponding rainbow saturation number. This is the saturation version of the rainbow Tur'an numbers whose systematic study was initiated by Keevash, Mubayi, Sudakov, and Verstra"ete. We give examples of graphs for which the rainbow saturation number is bounded away from the ordinary saturation number. This includes all complete graphs $K_n$ for $ngeq4$, and several bipartite graphs. It is notable that there are non-bipartite graphs for which this is the case, as this does not happen when it comes to the rainbow extremal number versus the traditional extremal number. We also show that saturation numbers are linear for a large class of graphs, providing a partial rainbow analogue of a well known theorem of K'asonyi and Tuza. We conclude this paper with related open questions and conjectures.

Recommendations

• Colored saturation parameters for rainbow subgraphs
• Rainbow saturation of graphs
• Rainbow saturation and graph capacities
• A note on rainbow saturation number of paths
• On edge-colored saturation problems

Cites work

• scientific article; zbMATH DE number 4081590 (Why is no real title available?)
• scientific article; zbMATH DE number 1179517 (Why is no real title available?)
• scientific article; zbMATH DE number 1409250 (Why is no real title available?)
• scientific article; zbMATH DE number 2192110 (Why is no real title available?)
• scientific article; zbMATH DE number 3414346 (Why is no real title available?)
• scientific article; zbMATH DE number 4185643 (Why is no real title available?)
• A Problem in Graph Theory
• Colored saturation parameters for rainbow subgraphs
• Lower bounds for rainbow Turan numbers of paths and other trees
• Many \(T\) copies in \(H\)-free graphs
• On the structure of linear graphs
• Rainbow Turán Problems
• Rainbow saturation and graph capacities
• Saturated graphs with minimal number of edges
• Size in maximal triangle-free graphs and minimal graphs of diameter 2

Cited in

(9)

• IPRainbow
• Rainbow saturation of graphs
• A note on rainbow saturation number of paths
• The rainbow saturation number is linear
• Colored saturation parameters for rainbow subgraphs
• Saturated rainbow edge colorings of cube graphs
• On edge-colored saturation problems
• Rainbow saturation and graph capacities
• Rainbow Saturation for Complete Graphs

This page was built for publication: Rainbow saturation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2084787)