Chromatic Number, Independence Ratio, and Crossing Number

Michael O. Albertson

Abstract


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.

Keywords


chromatic number, independence ratio, crossing number, dependent crossings

Full Text:

PDF ABSTRACTS (EN/SI)


ISSN: 1855-3974

Issues from Vol 6, No 1 onward are partially supported by the Slovenian Research Agency from the Call for co-financing of scientific periodical publications