A new approach to the chromatic number of the square of Kneser graph K(2k+1,k)
| Autor: | Jeong-Hyun Kang |
|---|---|
| Rok vydání: | 2018 |
| Předmět: |
Discrete mathematics
020206 networking & telecommunications 0102 computer and information sciences 02 engineering and technology 01 natural sciences Distance-regular graph Theoretical Computer Science Combinatorics Windmill graph 010201 computation theory & mathematics Graph power 0202 electrical engineering electronic engineering information engineering Wheel graph Discrete Mathematics and Combinatorics Bound graph Kneser graph Graph toughness Complement graph Mathematics |
| Zdroj: | Discrete Mathematics. 341:96-103 |
| ISSN: | 0012-365X |
| Popis: | The vertices of Kneser graph K ( n , k ) are the subsets of { 1 , 2 , … , n } of cardinality k , two vertices are adjacent if and only if they are disjoint. The square G 2 of a graph G is defined on the vertex set of G with two vertices adjacent if their distance in G is at most 2. Z. Furedi, in 2002, proposed the problem of determining the chromatic number of the square of the Kneser graph. The first non-trivial problem arises when n = 2 k + 1 . It is believed that χ ( K 2 ( 2 k + 1 , k ) ) = 2 k + c where c is a constant, and yet the problem remains open. The best known upper bounds are by Kim and Park: 8 k ∕ 3 + 20 ∕ 3 for 1 k ≥ 3 (Kim and Park, 2014) and 32 k ∕ 15 + 32 for k ≥ 7 (Kim and Park, 2016). In this paper, we develop a new approach to this coloring problem by employing graph homomorphisms, cartesian products of graphs, and linear congruences integrated with combinatorial arguments. These lead to χ ( K 2 ( 2 k + 1 , k ) ) ≤ 5 k ∕ 2 + c , where c is a constant in { 5 ∕ 2 , 9 ∕ 2 , 5 , 6 } , depending on k ≥ 2 . |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect