CATS-Jan-17-2014

Title

Defining sets in combinatorics with emphasis in graph theory

Speaker

E. S.Mahmoodian, Professor of Mathematics, Sharif University of Technology

Abstract

In a given graph $G$, a set of vertices $S$ with an assignment of colors is called a defining set (of a $k$--coloring), if there exists a unique extension of the colors of $S$ to a proper $k$-coloring of the vertices of $G$. A defining set with minimum cardinality is called a minimum defining set. The cardinality of minimum defining set is the defining number denoted by {$d(G, k)$}. A critical set is a minimal defining set. Defining sets are defined and discussed for many concepts and parameters in graph theory and combinatorics. For example in Latin squares a critical set is a partial Latin square that has a unique completion to a Latin square, and is minimal with respect to this property. Smallest possible size of a critical set in any Latin square of order $n$ is of interest and is denoted by $\scs{n}$. But it is clear that any $n \times n$ Latin square may be used as an $n$-coloring of the Cartesian product of ${K_n}$ by ${K_n}$ and vice versa. So \ d(${{K_n}\Box{K_n}},n$) = $\scs{n}$. The following conjecture which is made in 1995, is still open: For any $n$, \ $d({{K_n}\Box{K_n}},n) =\lfloor n^2/4 \rfloor$. In this talk we discuss these concepts in different areas and introduce some more open problems. Our emphasis will be in graph colorings and perfect matching. For some references and a survey, we refer to the author's webpage and papers referenced in there.

Web Accessibility