Hossein Hajiabolhassan: On Alternating Chromatic Number

In this talk, we introduce the alternating chromatic number of hypergraphs and we show that it provides a tight lower bound for the chromatic number of hypergraphs. Next, we introduce a colored version of the Turan number and use that to determine the chromatic number of some families of graphs. In particular, we introduce an extension of the well-known theorems of Lovasz (1978) and Schrijver (1978).

A Kneser representation KG(H) for a graph G is a bijective assignment of hyperedges of a hypergraph H to the vertices of G such that two vertices of G are adjacent if and only if the corresponding hyperedges are disjoint. Finally, we determine the chromatic number of every Kneser multigraph KG(H) where the vertex set of H is the edge set of a multigraph G such that the multiplicity of each edge is greater than 1 and a hyperedge in H corresponds to a subgraph of G isomorphic to some graph in a fixed prescribed family of simple graphs. (Joint work with Meysam Alishahi.)