Chromatic number, independence ratio, and crossing number - Albertson, Michael O. (Ars mathematica contemporanea, 2008)
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 ?$\frac{3}{16}$?.
Keywords: grafi; kromatično število; matematika; prekrižno število; teorija grafov