|
|
Межкафедральный семинар МФТИ по дискретной математике
18 декабря 2019 г. 17:00, г. Долгопрудный, МФТИ, Цифра, 2.35
|
|
|
|
|
|
Turán problems with dergee conditions
Б. Паткош |
|
Аннотация:
Turán problems ask for the maximum number $ex(n,F)$ of edges that an $n$-vertex graph $H$ can have without containing a copy of the forbidden graph $F$. These problems are the starting points of extremal graph theory and there have been an enormous amount of research in the area in the past century. There exist many generalizations and variants to this kind of problems. In my talk, I will survey some recently introduced notions and the first couple of results concerning these notions all of which involve the degrees of either all vertices of the graph $H$ or of all vertices of the copy of $F$ in $H$. More precisely, I will talk about the following problems.
- A subgraph $H$ of $G$ is singular if the vertices of $H$ either have the same degree in $G$ or have pairwise distinct degrees in $G$. The largest number of edges of a graph on $n$ vertices that does not contain a singular copy of $H$ is denoted by $T_S(n,H)$. We also explore the connection to the so-called $H$-WORM colorings (colorings without rainbow or monochromatic copies of $H$) and obtain new results regarding the largest number of edges that a graph with an $H$-WORM coloring can have.
- The regular Turán number $rex(n,F)$ is the maximum number of edges that an $n$-vertex regular graph $H$ can have without containing a copy of $F$.
`
|
|