Simonyi, Gábor (2020) On colorful edge triples in edge-colored complete graphs. GRAPHS AND COMBINATORICS, 36. pp. 1623-1637. ISSN 0911-0119
|
Text
1812.pdf Available under License Creative Commons Attribution. Download (193kB) | Preview |
Abstract
An edge-coloring of the complete graph Kn we call F-caring if it leaves no F-subgraph 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 2⌈log2n⌉ 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 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 > QA166-QA166.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 |
