Skip to main content
SUPERVISOR
Ramin Gavadi jourtani
رامین جوادی جورتانی (استاد راهنما)
 
STUDENT
Sepehr Hajebi
سپهر حاجبی

FACULTY - DEPARTMENT

دانشکده ریاضی
DEGREE
Master of Science (MSc)
YEAR
1395

TITLE

x- boundedness problems on graphs
For every graph $ G $ with chromatic number $ \\chi(G) $ and clique number $ \\ omega(G) $ , it is folklore that $ \\chi(G) \\geq \\omega (G) $ . The latter inequality naturally gives rise to two questions. First, for which graphs the chromatic number matches the clique number? Since the disjoint union of every graph $ G $ and a complete graph on $ \\chi (G) $ vertices results in a graph whose chromatic number equals its clique number , it would be sensible (and also promising) to ask for graphs whose all induced subgraphs possess chromatic number and clique number equal. Such graphs are called `` perfect quot;, firstly introduced by the French mathematician Claude Berge, and play an immensely important role in combinatorial optimization and theoretical computer science. One neater way to put the notion of perfection is utilizing the concept of an ``ideal quot; , i.e. a family of graphs closed under taking induced subgraphs. Therefore indeed the first question (in its more reasonable form) asks for a characterization of the ideal of perfect graphs, which is precisely done by the celebrated ``strong perfect graph theorem quot;. This theorem describes all minimally imperfect graphs (i.e. graphs which do not belong to the ideal of perfect graphs where all their induced subgraphs do so), asserting that odd cycles of length at least five and their complements are actually the only ones.
منظور از یک ایده‌آل ، خانواده‌ای از گراف‌ها است که تحت شمول زیرگراف القایی بسته باشد. برای هر گراف با عدد رنگی و عدد خوشه‌ای ، می‌دانیم همواره .نابرابری اخیر دو پرسش طبیعی را به ذهن متبادر می‌سازد. نخست آن که برای کدام گراف‌ها عدد رنگی و عدد خوشه‌ای برابر هستند؟ به دلایل فنی ، مطلوبِ این پرسش مبدل به جستجو برای یک مشخص سازی از ایده‌آل گراف‌های با عدد رنگی و عدد خوشه‌ای برابر شده ، این جستجو منجر به تولد نظریه گراف‌های بی‌نقص می‌گردد ، که در مرکز آن قضیه قوی گراف‌های بی‌نقص به عنوان یک مشخص سازی از ایده‌آل گراف‌های بی‌نقص بر حسب زیرگراف‌های القایی ممنوعه مینیمال نظیر آن ایفای نقش می‌کند. دوم آن که آیا کران بالایی کلی برای عدد رنگی یک گراف برحسب عدد خوشه‌ای آن وجود دارد؟ پاسخ به این پرسش بنابر وجود گراف‌های فاقد مثلث با عدد رنگی به قدر دلخواه بزرگ ، منفی است. بر این اساس ، ایده‌آل از گراف‌ها را -کراندار گوییم هر گاه تا بع موجود باشد به طوری که برای هر ، داشته باشیم . در این رساله ، به پیروی از رهیافت قضیه قوی گراف‌های بی‌نقص، به طور مشروح به مطالعه نتایج و حدس‌های موجود در باب مشخص سازی ایده‌آل‌های -کراندار بر حسب گراف‌های ممنوعه مینیمال نظیر آن‌ها می‌پردازیم. به طور خاص ، این مطالعه را در دو حالت ، برحسب متناهی بودن یا نبودن تعداد گراف‌های ممنوعه مینیمال نظیر ایده‌آل مورد نظر ، انجام خواهیم داد.

ارتقاء امنیت وب با وف بومی