On thec-strong chromatic number oft-intersecting hypergraphs
| Autor: | Ping Ngai Chung |
|---|---|
| Rok vydání: | 2013 |
| Předmět: |
Discrete mathematics
Hypergraph Mathematics::Combinatorics Strong coloring Complete coloring Theoretical Computer Science Vertex (geometry) Combinatorics Intersection Computer Science::Discrete Mathematics Weak coloring Discrete Mathematics and Combinatorics Chromatic scale Fractional coloring Mathematics |
| Zdroj: | Discrete Mathematics. 313:1063-1069 |
| ISSN: | 0012-365X |
| Popis: | For a fixed c ≥ 2 , a c -strong coloring of the hypergraph G is a vertex coloring such that each edge e of G covers vertices with at least min { c , | e | } distinct colors. A hypergraph is t -intersecting if the intersection of any two of its edges contains at least t vertices. This paper addresses the question: what is the minimum number of colors which suffices to c -strong color any t -intersecting hypergraph? We first show that the number of colors required to c -strong color a hypergraph of size n is O ( n ) . Then we prove that we can use finitely many colors to 3-strong color any 2-intersecting hypergraph. Finally, we show that 2 c − 1 colors are enough to c -strong color any shifted ( c − 1 ) -intersecting hypergraph, and 2 c − 2 colors are enough to c -strong color any shifted t -intersecting hypergraph for t ≥ c . Both chromatic numbers are optimal and match conjectured statements in which the shifted condition is removed. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect