Sobre coloração total de grafos Kneser e de grafos produto direto de completos e de ciclos

Abstract

In this thesis, the total chromatic number in three classes of graphs is studied: Kneser graphs, direct product of complete graphs and direct product of cycle graphs. In the class of Kneser graphs K(n, s), we show that the most sparse connected K(2k − 1, k − 1), known as Odd Graphs, are Type 1 and we prove that the dense Kneser graphs K(n, 2) satisfy the TCC when n is even, or when n is odd and not divisible by 3. For the remaining cases when n is odd and divisible by 3, we get a total coloring of K(n, 2) with ∆(K(n, 2)) + 3 colors when n ≡ 3 mod 4, and with ∆(K(n, 2)) + 4 colors when n ≡ 1 mod 4. In addition, we present an infinite family of Kneser graphs K(n, 2) that have the chromatic index equal to ∆(K(n, 2)). For the direct product of complete graphs Km × Kn, it is known that if at least one of the numbers m or n are even, then Km × Kn is Type 1, except for K2 × K2. We prove that the graph Km × Kn is Type 1 when m and n are odd, ensuring in this way that all graphs Km × Kn are Type 1, except for K2 × K2. Additionally, for the direct product of cycle graphs Cm × Cn, particular cases of Cm × Cn, for m = 3p, 5` and 8` with p ≥ 2 and ` ≥ 1, and n ≥ 3, were previously known to be Type 1. This result motivated the conjecture that, except for C4 × C4, the direct product Cm ×Cn with m, n ≥ 3 is Type 1. We establish merge techniques to prove that all Cm ×Cn are Type 1, except for C4 ×C4. In addition, we investigate conditions that can help us to verify that the direct product of any two graphs reaches the lower bound for the total chromatic number.