Simonyi, Gábor (2020) On colorful edge triples in edgecolored complete graphs. GRAPHS AND COMBINATORICS, 36. pp. 16231637. ISSN 09110119

Text
1812.pdf Available under License Creative Commons Attribution. Download (193kB)  Preview 
Abstract
An edgecoloring of the complete graph Kn we call Fcaring 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 Fcaring edgecoloring of Kn. An explicit family of 2⌈log2n⌉ 3edgecolorings 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 Ramseytype problems we also show that the Shannon (OR)capacity of the Grötzsch graph is strictly larger than that of the five length cycle.
Item Type:  Article 

Subjects:  Q Science / természettudomány > QA Mathematics / matematika Q Science / természettudomány > QA Mathematics / matematika > QA166QA166.245 Graphs theory / gráfelmélet 
SWORD Depositor:  MTMT SWORD 
Depositing User:  MTMT SWORD 
Date Deposited:  23 Nov 2020 11:46 
Last Modified:  24 Apr 2023 11:04 
URI:  http://real.mtak.hu/id/eprint/117256 
Actions (login required)
Edit Item 