Rainbow saturation

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

Authors: Yanyan Li 

Publication date: 13 October 2022

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

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.

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

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

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)

Cites Work

• Title not available (Why is that?)
• On the structure of linear graphs
• Saturated graphs with minimal number of edges
• A Problem in Graph Theory
• Rainbow Turán Problems
• Title not available (Why is that?)
• Title not available (Why is that?)
• Size in maximal triangle-free graphs and minimal graphs of diameter 2
• Many \(T\) copies in \(H\)-free graphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Rainbow saturation and graph capacities
• Colored saturation parameters for rainbow subgraphs
• Lower bounds for rainbow Turan numbers of paths and other trees

Cited In (9)

• IPRainbow
• Rainbow saturation of graphs
• The rainbow saturation number is linear
• Saturated rainbow edge colorings of cube graphs
• A note on rainbow saturation number of paths
• On edge-colored saturation problems
• Colored saturation parameters for rainbow subgraphs
• 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)