1. bookAHEAD OF PRINT
Zeitschriftendaten
License
Format
Zeitschrift
eISSN
2083-5892
Erstveröffentlichung
13 Apr 2013
Erscheinungsweise
4 Hefte pro Jahr
Sprachen
Englisch
access type Uneingeschränkter Zugang

An Upper Bound on the Chromatic Number of 2-Planar Graphs

Online veröffentlicht: 18 Mar 2021
Volumen & Heft: AHEAD OF PRINT
Seitenbereich: -
Eingereicht: 21 Aug 2020
Akzeptiert: 08 Feb 2021
Zeitschriftendaten
License
Format
Zeitschrift
eISSN
2083-5892
Erstveröffentlichung
13 Apr 2013
Erscheinungsweise
4 Hefte pro Jahr
Sprachen
Englisch
Abstract

It is proved that any 2-planar graph (i.e., a graph which can be drawn on a plane such that any edge intersects at most two others) has a proper vertex coloring with 9 colors.

MSC 2010

[1] G. Ringel, Ein Sechsfarbenproblem auf der Kugel, Abh. Math. Semin. Univ. Hambg. 29 (1965) 107–117. doi:10.1007/BF0299631310.1007/BF02996313Search in Google Scholar

[2] J. Pach and G. Tóth, Graphs drawn with few crossing per edge, Combinatorica 17 (1997) 427–439. doi:10.1007/BF0121592210.1007/BF01215922Search in Google Scholar

[3] O.V. Borodin, A solution of Ringel’s problem on vertex-face coloring of plane graphs and on coloring of 1-planar graphs, Metody Diskret. Analiz. 41 (1984) 12–26, (in Russian).Search in Google Scholar

[4] D.V. Karpov, On plane drawings of 2-planar graphs, Zap. Nauchn. Sem. S.-Petersburg. Otdel. Mat. Inst. Steklov 488 (2019) 49–65.Search in Google Scholar

Empfohlene Artikel von Trend MD

Planen Sie Ihre Fernkonferenz mit Scienceendo