图 书 馆
几乎平面图的独立性比率Independence ratios of nearly planar graphs |
|
| 课程网址: | http://videolectures.net/sicgt07_albertson_ironpg/ |
| 主讲教师: | Michael Albertson |
| 开课单位: | 史密斯学院 |
| 开课时间: | 2007-09-07 |
| 课程语种: | 英语 |
| 中文简介: |  |
| 课程简介: | With purposeful imprecision, a graph is said to be nearly planar if it resembles in some essential way a planar graph. Classic measures of near planarity include the thickness, the crossing number, and the genus. Modern versions of nearly planar graphs include the graphs embedded on surfaces with large width (shortest noncontractible cycle). Geometric graph theory has given us a different notion of locally planar as well as two definitions of quasi-planar graphs. This talk will begin with a retrospective look at independence ratios of locally planar graphs. We consider contrasts between results about the independence ratio and those about the chromatic number. We will then proceed to results and open questions about independence ratios of various classes of nearly planar graphs. |
| 关 键 词: | 平面图; 独立性; 色数 |
| 课程来源: | 视频讲座网 |
| 最后编审: | 2019-09-17：lxf |
| 阅读次数: | 75 |