Rainbow saturation

DOI10.1007/S00373-022-02566-ZMaRDI QIDQ2084787zbMATH OpenOpenAlexFDO

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

edge coloringextremal graph theorysaturation

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Extremal problems in graph theory (05C35) 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

• A Problem in Graph Theory
• Colored saturation parameters for rainbow subgraphs
• 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?)
• 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 saturation and graph capacities
• Rainbow Turán Problems
• Saturated graphs with minimal number of edges
• Size in maximal triangle-free graphs and minimal graphs of diameter 2

Cited in

(12)

• A note on rainbow saturation number of paths
• On edge-colored saturation problems
• Saturated rainbow edge colorings of cube graphs
• Rainbow saturation and graph capacities
• Colored saturation parameters for rainbow subgraphs
• Rainbow saturation of graphs
• Rainbow Saturation for Complete Graphs
• IPRainbow
• The rainbow saturation number is linear
• Improved bounds for proper rainbow saturation
• Weak rainbow saturation numbers of graphs
• On the proper rainbow saturation numbers of cliques, paths, and odd cycles

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)