• Title of article

    Coloring graphs with crossings

  • Author/Authors

    Oporowski، نويسنده , , Bogdan and Zhao، نويسنده , , David، نويسنده ,

  • Issue Information
    روزنامه با شماره پیاپی سال 2009
  • Pages
    4
  • From page
    2948
  • To page
    2951
  • 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.
  • Keywords
    clique number , chromatic number , crossing number , IMMERSION
  • Journal title
    Discrete Mathematics
  • Serial Year
    2009
  • Journal title
    Discrete Mathematics
  • Record number

    1598781