On colorful edge triples in edge-colored complete graphs

DOI10.1007/S00373-020-02214-4MaRDI QIDQ2657036zbMATH OpenOpenAlexFDO

Authors Gábor Simonyi

Publication date 17 March 2021

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

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

Kirkman triple systemsMycielski constructionRamsey coloringsShannon capacity

Mathematics Subject Classification ID

Triple systems (05B07) Generalized Ramsey theory (05C55) Graph operations (line graphs, products, etc.) (05C76) Coding theorems (Shannon theory) (94A24)

Abstract: An edge-coloring of the complete graph $K_n$ we call $F$-caring if it leaves no $F$-subgraph of $K_n$ 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=K_{1,3}$ and $F=P_4$ we determine for infinitely many $n$ the minimum number of colors needed for an $F$-caring edge-coloring of $K_n$. An explicit family of $2lceillo{g}_{2}nceil$ $3$-edge-colorings of $K_n$ so that every quadruple of its vertices contains a totally multicolored $P_4$ 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"otzsch graph is strictly larger than that of the five length cycle.

Recommendations

• scientific article; zbMATH DE number 5717204
• scientific article; zbMATH DE number 5995288
• Sufficient conditions for properly colored \(C_3\)'s and \(C_4\)'s in edge-colored complete graphs
• Rainbow triangles and cliques in edge-colored graphs
• scientific article; zbMATH DE number 434896

Cites work

• A nontrivial lower bound on the shannon capacities of the complements of odd cycles
• A survey of Kirkman triple systems and related designs
• A variant of the classical Ramsey problem
• An explicit construction for a Ramsey problem
• Anti-Ramsey colorings in several rounds
• Constructive lower bounds on classical multicolor Ramsey numbers
• Edge-colorings avoiding rainbow and monochromatic subgraphs
• Fredman–Komlós bounds and information theory
• Hall ratio of the Mycielski graphs
• scientific article; zbMATH DE number 3763932 (Why is no real title available?)
• scientific article; zbMATH DE number 1131467 (Why is no real title available?)
• scientific article; zbMATH DE number 863469 (Why is no real title available?)
• scientific article; zbMATH DE number 881164 (Why is no real title available?)
• scientific article; zbMATH DE number 3430675 (Why is no real title available?)
• I. Schur, C. E. Shannon and Ramsey numbers, a short story
• Kneser's conjecture, chromatic number, and homotopy
• New bounds for perfect hashing via information theory
• On generalized Ramsey theory: The bipartite case
• On resolvable designs
• On the Shannon capacity of a graph
• On the Size of Separating Systems and Families of Perfect Hash Functions
• Orientations making \(k\)-cycles cyclic
• Orientations of self-complementary graphs and the relation of Sperner and Shannon capacities
• Qualitative independence and Sperner problems for directed graphs
• Ramsey bounds for graph products
• Repeated communication and Ramsey graphs
• Separating Partition Systems and Locally Different Sequences
• String quartets in binary
• Sur le coloriage des graphs
• Zero error capacity under list decoding

Cited in

(7)

• Partial triple systems and edge colourings
• The inclusion-free edge-colorings of \((3, \varDelta)\)-bipartite graphs
• On hyperedge coloring of weakly trianguled hypergraphs and well ordered hypergraphs
• The edge cover chromatic index of complete tripartite graphs
• scientific article; zbMATH DE number 3873373 (Why is no real title available?)
• On the maximal triangle-free edge-chromatic graphs in three colors
• 3-consecutive edge coloring of a graph

This page was built for publication: On colorful edge triples in edge-colored complete graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2657036)