Seminar

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

Program
Contact

Klas Markström

klas.markstrom@math.umu.se

Other
information

For practical matters at the Institute, send an e-mail to secretary@mittag-leffler.se