Chromatic number, independence ratio, and crossing number
Chromatic number, independence ratio, and crossing number
复制标题
DOI：
10.26493/1855-3974.10.2d0
复制
发表时间：
2008-06
期刊：
影响因子：
--
通讯作者：
M. Albertson
中科院分区：
文献类型：
--
作者：
M. Albertson
给定一个图G的图，如果两个交点与同一个顶点相交，则称它们是相关的。如果没有两个交叉点相互依赖，则一组交叉点是独立的。我们推测，如果G是一个图形，它所有的交叉点都是独立的，那么G的色数最多为5。我们证明，如果G的交叉数不超过3，这个猜想是成立的。我们还证明了如果所有交叉是独立的，那么G的色数最多为6，G的独立比至少为3/16。
Given a drawing of a graph G, two crossings are said to be dependent if they are incident with the same vertex. A set of crossings is independent if no two are dependent. We conjecture that if G is a graph that has a drawing all of whose crossings are independent, then the chromatic number of G is at most 5. We show that this conjecture is true if the crossing number of G is at most three. We also show that if all crossings are independent, then the chromatic number of G is at most 6, and the independence ratio of G is at least 3/16.