DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

https://doi.org/10.7151/dmgt

Discussiones Mathematicae Graph Theory

Journal Impact Factor (JIF 2022): 0.7

5-year Journal Impact Factor (2022): 0.7

CiteScore (2022): 1.9

SNIP (2022): 0.902

Discussiones Mathematicae Graph Theory

Article in volume

Authors:

D.V. Karpov

Dmitri V. Karpov

St. Petersburg Department of V.A.Steklov Institute of Mathematics of the Russian Academy of Sciences
and
St.Petersburg University

email: dvk0@yandex.ru

Title:

An upper bound on the chromatic number of 2-planar graphs

PDF

Source:

Discussiones Mathematicae Graph Theory 43(3) (2023) 703-720

Received: 2020-08-21 , Revised: 2021-02-07 , Accepted: 2021-02-08 , Available online: 2021-03-04 , https://doi.org/10.7151/dmgt.2397

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.

Keywords:

2-planar graphs, chromatic number

References:

  1. G. Ringel, Ein Sechsfarbenproblem auf der Kugel, Abh. Math. Semin. Univ. Hambg. 29 (1965) 107–117.
    https://doi.org/10.1007/BF02996313
  2. J. Pach and G. Tóth, Graphs drawn with few crossing per edge, Combinatorica 17 (1997) 427–439.
    https://doi.org/10.1007/BF01215922
  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).
  4. D.V. Karpov, On plane drawings of $2$-planar graphs, Zap. Nauchn. Sem. S.-Petersburg. Otdel. Mat. Inst. Steklov 488 (2019) 49–65.
Close