University of Primorska
Faculty of Mathematics, Natural Sciences and Information Technologies
10.05.2012 Lecturer: Nina Chiarelli
Title: Split graphs and threshold graphs
Abstract: The chromatic number of a graph is the minimum number of colors needed to color the vertices of the graph in such a way that no adjacent vertices have the same color. A clique in a graph is a subset of pairwise adjacent vertices. Graphs for which the chromatic number
of every induced subgraph is equal to the size of its largest clique, are called perfect graphs. In this talk we will give basic definitions and present different characterizations (with forbidden induced subgraphs and with degree sequences) for split graphs and threshold graphs, two of the many families of perfect graphs.
of every induced subgraph is equal to the size of its largest clique, are called perfect graphs. In this talk we will give basic definitions and present different characterizations (with forbidden induced subgraphs and with degree sequences) for split graphs and threshold graphs, two of the many families of perfect graphs.