On Colorful Edge Triples in Edge-Colored Complete Graphs
- PDF / 328,345 Bytes
- 15 Pages / 439.37 x 666.142 pts Page_size
- 46 Downloads / 177 Views
(0123456789().,-volV)(0123456789().,-volV)
ORIGINAL PAPER
On Colorful Edge Triples in Edge-Colored Complete Graphs Ga´bor Simonyi1,2 Received: 17 December 2018 / Revised: 26 June 2020 Ó The Author(s) 2020
Abstract An edge-coloring of the complete graph Kn we call F-caring if it leaves no Fsubgraph of Kn monochromatic and at the same time every subset of |V(F)| vertices contains in it at least one completely multicolored version of F. For the first two meaningful cases, when F ¼ K1;3 and F ¼ P4 we determine for infinitely many n the minimum number of colors needed for an F-caring edge-coloring of Kn . An explicit family of 2dlog2 ne 3-edge-colorings of Kn so that every quadruple of its vertices contains a totally multicolored P4 in at least one of them is also presented. Investigating related Ramsey-type problems we also show that the Shannon (OR)capacity of the Gro¨tzsch graph is strictly larger than that of the cycle of length 5. Keywords Ramsey colorings Kirkman triple systems Shannon capacity Mycielski construction
Mathematics Subject Classification 05C55 05B07 05C76
1 Introduction Erd}os [12] formulated the following Ramsey type problem: What is the least number f(n, p, q) of colors needed for an edge-coloring of the complete graph Kn if it has the property that every subset of p vertices spans at least q distinct colors? Initial investigations by Elekes, Erd}os, and Fu¨redi reported in [12] were followed by a more systematic study by Erd}os and Gya´rfa´s in [13]. A more general variant of the Research partially supported by the National Research, Development and Innovation Office (NKFIH) grants K-116769, K-120706, K-132696, BME NC TKP2020, by the National Research, Development and Innovation Fund (TUDFO/51757/2019-ITM, Thematic Excellence Program), and by the BMEArtificial Intelligence FIKP grant of EMMI (BME FIKP-MI/SC). This work is also connected to the scientific program of the ‘‘Development of quality-oriented and harmonized R?D?I strategy and functional model at BME’’ project, supported by the New Hungary Development Plan (Project ID: ´ MOP-4.2.1/B-09/1/KMR-2010-0002) TA Extended author information available on the last page of the article
123
Graphs and Combinatorics
problem was studied by Axenovich, Fu¨redi, and Mubayi [3], where they color the edges of a not necessarily complete graph G and require that every copy of another graph H G receive at least a given number of colors. Axenovich and Iverson [4] investigated the mixed anti-Ramsey numbers that are the maximum and minimum numbers of colors to be used in an edge-coloring of Kn that avoids both monochromatic copies of a fixed graph G and also totally multicolored copies of another fixed graph H. Here we initiate the investigation of yet another variant that will also be connected to some of the above versions of the classical Ramsey problem. Let g(n, F) denote the minimum number of colors needed in an edge-coloring of Kn if it contains no monochromatic copy of F, furthermore, it contains at least one totally multicolored copy of
Data Loading...
