| Thursday 25 April 2024 | |
| Events for day: Wednesday 27 April 2022 |
| 14:00 - 16:00 Combinatorics and Computing Weekly Seminar A Catlin-type Theorem for G-free Coloring of Graphs School MATHEMATICS Let G be a connected graph of order at least 2. A G-free k-coloring of a graph H is a partition of the vertex set of H into V1, . . . , Vk such that H[Vi], the subgraph induced on Vi, does not contain any subgraph isomorphic to G. Catlin in 1979 showed that if H is neither an odd cycle nor a complete graph with maximum degree ∆(H), then H has a vertex ∆(H)- coloring such that one of the color classes is a maximum independent set. As a generalization of Catlin?s Theorem, under some assumptions we show that a graph H has a G-free d ∆(H) δ(G) ecoloring for which one of the color classes is a maximum G-free subset o ... |