Gallai-Colorings of Triples and 2-Factors of B[subscript 3]
A coloring of the edges of the r-uniform complete hypergraph is a G[subscript r]-coloring if there is no rainbow simplex; that is, every set of r + l vertices contains two edges of the same color. The notion extends G[subscript 2]-colorings which are often called Gallai-colorings and originates from...
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
Hindawi Publishing Corporation
2015
|
| Online Access: | http://hdl.handle.net/1721.1/96125 |
| _version_ | 1826200490596106240 |
|---|---|
| author | Chua, Lynn Gyarfas, Andras Hossain, Chetak |
| author2 | Massachusetts Institute of Technology. Department of Mathematics |
| author_facet | Massachusetts Institute of Technology. Department of Mathematics Chua, Lynn Gyarfas, Andras Hossain, Chetak |
| author_sort | Chua, Lynn |
| collection | MIT |
| description | A coloring of the edges of the r-uniform complete hypergraph is a G[subscript r]-coloring if there is no rainbow simplex; that is, every set of r + l vertices contains two edges of the same color. The notion extends G[subscript 2]-colorings which are often called Gallai-colorings and originates from a seminal paper of Gallai. One well-known property of G[subscript 2]-colorings is that at least one color class has a spanning tree. J. Lehel and the senior author observed that this property does not hold for G[subscript r]-colorings and proposed to study f[subscript r](n), the size of the largest monochromatic component which can be found in every G[subscript r]-coloring of K[r over n], the complete r-uniform hypergraph. The previous remark says that f[subscript 2](n) = n, and in this note, we address the case r = 3. We prove that [(n + 3)/2] ≤ f[subscript 3](n) ≤ [4n/5], and this determines f[subscript 3](n) for n < 7. We also prove that f[subscript 3](7) = 6 by excluding certain 2-factors from the middle layer of the Boolean lattice on seven elements. |
| first_indexed | 2024-09-23T11:37:17Z |
| format | Article |
| id | mit-1721.1/96125 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T11:37:17Z |
| publishDate | 2015 |
| publisher | Hindawi Publishing Corporation |
| record_format | dspace |
| spelling | mit-1721.1/961252022-10-01T04:49:03Z Gallai-Colorings of Triples and 2-Factors of B[subscript 3] Chua, Lynn Gyarfas, Andras Hossain, Chetak Massachusetts Institute of Technology. Department of Mathematics Chua, Lynn A coloring of the edges of the r-uniform complete hypergraph is a G[subscript r]-coloring if there is no rainbow simplex; that is, every set of r + l vertices contains two edges of the same color. The notion extends G[subscript 2]-colorings which are often called Gallai-colorings and originates from a seminal paper of Gallai. One well-known property of G[subscript 2]-colorings is that at least one color class has a spanning tree. J. Lehel and the senior author observed that this property does not hold for G[subscript r]-colorings and proposed to study f[subscript r](n), the size of the largest monochromatic component which can be found in every G[subscript r]-coloring of K[r over n], the complete r-uniform hypergraph. The previous remark says that f[subscript 2](n) = n, and in this note, we address the case r = 3. We prove that [(n + 3)/2] ≤ f[subscript 3](n) ≤ [4n/5], and this determines f[subscript 3](n) for n < 7. We also prove that f[subscript 3](7) = 6 by excluding certain 2-factors from the middle layer of the Boolean lattice on seven elements. 2015-03-20T16:14:47Z 2015-03-20T16:14:47Z 2013 2013-06 2015-03-19T11:35:02Z Article http://purl.org/eprint/type/JournalArticle 1687-9163 1687-9171 http://hdl.handle.net/1721.1/96125 Chua, Lynn, Andras Gyarfas, and Chetak Hossain. “Gallai-Colorings of Triples and 2-Factors of B[subscript 3].” International Journal of Combinatorics 2013 (2013): 1–6. en http://dx.doi.org/10.1155/2013/929565 International Journal of Combinatorics Creative Commons Attribution http://creativecommons.org/licenses/by/2.0 Copyright © 2013 Lynn Chua et al. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited. application/pdf Hindawi Publishing Corporation Hindawi Publishing Corporation |
| spellingShingle | Chua, Lynn Gyarfas, Andras Hossain, Chetak Gallai-Colorings of Triples and 2-Factors of B[subscript 3] |
| title | Gallai-Colorings of Triples and 2-Factors of B[subscript 3] |
| title_full | Gallai-Colorings of Triples and 2-Factors of B[subscript 3] |
| title_fullStr | Gallai-Colorings of Triples and 2-Factors of B[subscript 3] |
| title_full_unstemmed | Gallai-Colorings of Triples and 2-Factors of B[subscript 3] |
| title_short | Gallai-Colorings of Triples and 2-Factors of B[subscript 3] |
| title_sort | gallai colorings of triples and 2 factors of b subscript 3 |
| url | http://hdl.handle.net/1721.1/96125 |
| work_keys_str_mv | AT chualynn gallaicoloringsoftriplesand2factorsofbsubscript3 AT gyarfasandras gallaicoloringsoftriplesand2factorsofbsubscript3 AT hossainchetak gallaicoloringsoftriplesand2factorsofbsubscript3 |