자료유형 | 학위논문 |
---|---|
서명/저자사항 | Cliques, Stable Sets, And Coloring In Graphs with Forbidden Induced Subgraphs. |
개인저자 | Spirkl, Sophie Theresa. |
단체저자명 | Princeton University. Applied and Computational Mathematics. |
발행사항 | [S.l.]: Princeton University., 2018. |
발행사항 | Ann Arbor: ProQuest Dissertations & Theses, 2018. |
형태사항 | 209 p. |
기본자료 저록 | Dissertation Abstracts International 79-10B(E). Dissertation Abstract International |
ISBN | 9780438048256 |
학위논문주기 | Thesis (Ph.D.)--Princeton University, 2018. |
일반주기 |
Source: Dissertation Abstracts International, Volume: 79-10(E), Section: B.
Advisers: Maria Chudnovsky |
요약 | The Gyarfas-Sumner conjecture [29, 42] states that for every tree T there is a function f such that for every graph G with no induced subgraph isomorphic to T the chromatic number of G is at most f(o(G)), where o(G) is its clique number. We pro |
요약 | A class C of graphs has the EH-property if there is a delta > 0 such that every G &isin |
요약 | The strong perfect graph theorem [11] contains a decomposition theorem, and even though perfect graphs can be colored in polynomial time [28], no combinatorial algorithm for this is known. One obstacle for such an algorithm are "skew partitions" |
일반주제명 | Mathematics. |
언어 | 영어 |
바로가기 | ![]() |