0 KB138 KB15 KB200820252008Albertson, Michael O.številka:1letnik:1str. 1-6COBISSID:15110745ISSN:1855-3966URN:URN:NBN:SI:doc-ADNJPTM6enDruštvo matematikov, fizikov in astronomov SlovenijeArs mathematica contemporaneagrafikromatično številomatematikaprekrižno številoteorija grafovChromatic number, independence ratio, and crossing number|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}$?TEXTznanstveno časopisjejournalsSlovenian National E-content AggregatorNational and University Library of SloveniaUniverza na Primorskem, Fakulteta za naravoslovje, matematiko in informacijske tehnologije