On Alternating Chromatic Number

Graphs, Hypergraphs, and Computing

15 April 15:30 - 16:30

Hossein Hajiabolhassan - Technical University of Denmark, DTU

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)
Magnus M. Halldorsson
Reykjavik University
Klas Markström
Umeå University
Andrzej Rucinski
Adam Mickiewicz University
Carsten Thomassen
Technical University of Denmark, DTU


Klas Markström


For practical matters at the Institute, send an e-mail to