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}$?.

Rights

URN

URN:NBN:SI:doc-ADNJPTM6

COBISSID

15110745

Added

16.12.2021

Metadata

Citation

APA:

Albertson, Michael O. (2008). Chromatic number, independence ratio, and crossing number. Ars mathematica contemporanea, volume 1, issue 1, str. 1-6. URN:NBN:SI:doc-ADNJPTM6 from http://www.dlib.si

MLA:

Albertson, Michael O.. "Chromatic number, independence ratio, and crossing number." Ars mathematica contemporanea volume 1. issue 1 (2008) str. 1-6.
<http://www.dlib.si/?URN=URN:NBN:SI:doc-ADNJPTM6>

Ars mathematica contemporanea
2008-
(Assembly record)