Bureaucrats, editor, Administrators
373
edits
Changes
From Theory
Created page with "== Title == Defining sets in combinatorics with emphasis in graph theory == Speaker == E. S.Mahmoodian, Professor of Mathematics, Sharif University of Technology == Abstra..."
== 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 {\em 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 {\em minimum
defining set.} The cardinality of minimum defining set is the
{\em defining number} denoted by {$d(G, k)$}. A {\em 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 {\em{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.
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 {\em 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 {\em minimum
defining set.} The cardinality of minimum defining set is the
{\em defining number} denoted by {$d(G, k)$}. A {\em 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 {\em{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.
