descriptionPublicationkeyboard_double_arrow_right Article , Preprint 01 May 2009Embargo end date: 01 Jan 2005 English Publisher:Elsevier BVJournal:Discrete Mathematics, volume 309, pages 2,948-2,951 (issn: 0012-365X,

Authors: Bogdan Oporowski; David Zhao;

doi: 10.1016/j.disc.2008.07.040 , 10.48550/arxiv.math/0501427

arXiv: http://arxiv.org/abs/math/0501427

Coloring graphs with crossings

- Summary
- Subjects
- Metrics

Abstract

We generalize the Five Color Theorem by showing that it extends to graphs with two crossings. Furthermore, we show that if a graph has three crossings, but does not contain K_6 as a subgraph, then it is also 5-colorable. We also consider the question of whether the result can be extended to graphs with more crossings.

5 pages

Related Organizations

The University of Texas at Austin
United States
Louisiana State University
United States
The University of Texas System
United States

Keywords

05C15, Crossing number, Immersion, FOS: Mathematics, Chromatic number, Discrete Mathematics and Combinatorics, Mathematics - Combinatorics, Combinatorics (math.CO), Clique number, Theoretical Computer Science

Impact byBIP!

	citations This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	6
	popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.	Average
	influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	Average
	impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.	Average

Found an issue? Give us feedback

Average

Green

hybrid

Fields of Science (3) View all

Fields of Science