turkmath.org

Türkiye'deki Matematiksel Etkinlikler


13 Kasım 2020, 15:00


Boğaziçi Üniversitesi Matematik Lisansüstü Seminerleri

Defective Ramsey Numbers and Cocolorings on Graph Classes

Mehmet Akif Yıldız
Boğaziçi Üniversitesi, Türkiye

In extremal graph theory, $R(i,j)$ is defined as the smallest integer $n$ such that any simple undirected graph on $n$ vertices has either a clique of size $i$ or an independent set of size $j$, and $c(m)$ is defined as the greatest integer $r$ such that every graph on $r$ vertices can be partitioned into $m$ subsets where each subset induces either a clique or an independent set. These parameters are well-studied in the literature, but their exact values are known only for smaller values of $i$, $j$, $m$. However, it may be possible to find exact formulas for $R(i,j)$ and $c(m)$ when they are examined on some graph classes such as perfect graphs.

As a relaxation of the notions clique and independent set, one can define \textit{$k$-defective} sets. A \textit{$k$-sparse $i$-set} is a set $S$ of $i$ vertices of a graph $G$ such that each vertex in $S$ has degree at most $k$ in $G$. Similarly, a \textit{$k$-dense $j$-set} is a set $D$ of $j$ vertices of a graph $G$ such that each vertex in $D$ has degree at most $k$ in the complement of $G$; in other words, each vertex in $D$ misses at most $k$ other vertices in its neighborhood. The term $k-$defective is used to denote a $k$-sparse or $k$-dense set, and note that $0$-dense and $0$-sparse sets correspond to cliques and independent sets, respectively.

Let $R_k^{\mathcal{G}}(i,j)$ be the smallest natural number $n$ such that every graph in the class $\mathcal{G}$ on $n$ vertices has either a $k$-dense $i$-set or a $k$-sparse $j$-set, and $c_k^{\mathcal{G}}(m)$ be greatest integer $r$ such that every graph in the class $\mathcal{G}$ on $r$ vertices can be partitioned into $m$ subsets where each subset induces a $k$-defective set. The talk will be about some partial results on $R_k^{\mathcal{G}}(i,j)$ and $c_k^{\mathcal{G}}(m)$ when $\mathcal{G}$ represents perfect graphs, or some of its subclasses such as cographs and split graphs.

This is joint work with T{\i}naz Ekim, John Gimbel and Yunus Emre Demirci.


NOT: Zoom Meeting ID: 971 7887 1153 / Passcode: BounMath

Matematik İngilizce
Zoom
İlgili Web Bağlantısı

osavk 09.11.2020

Yaklaşan Seminerler Seminer Arşivi
 

İLETİŞİM

Akademik biriminizin ya da çalışma grubunuzun ülkemizde gerçekleşen etkinliklerini, ilan etmek istediğiniz burs, ödül, akademik iş imkanlarını veya konuk ettiğiniz matematikçileri basit bir veri girişi ile kolayca turkmath.org sitesinde ücretsiz duyurabilirsiniz. Sisteme giriş yapmak için gerekli bilgileri almak ya da görüş ve önerilerinizi bildirmek için iletişime geçmekten çekinmeyiniz. Katkı verenler listesi için tıklayınız.

Özkan Değer ozkandeger@gmail.com

DESTEK VERENLER

ja2019

31. Journees Arithmetiques Konferansı Organizasyon Komitesi

Web sitesinin masraflarının karşılanması ve hizmetine devam edebilmesi için siz de bağış yapmak, sponsor olmak veya reklam vermek için lütfen iletişime geçiniz.

ONLİNE ZİYARETÇİLER


©2013-2020 turkmath.org
Tüm hakları saklıdır