Sciact
  • EN
  • RU

A new 4-chromatic edge critical Koester graph Full article

Journal Discrete Mathematics Letters
ISSN: 2664-2557
Output data Year: 2023, Volume: 12, Pages: 6-10 Pages count : 5 DOI: 10.47443/dml.2022.166
Tags plane graph; 4-critical graph; Gro¨tzsch–Sachs graph; Koester graph
Authors Dobrynin Andrey A. 1
Affiliations
1 Sobolev Institute of Mathematics, Siberian Branch of the Russian Academy of Sciences, Novosibirsk 630090, Russia

Funding (1)

1 Sobolev Institute of Mathematics FWNF-2022-0017

Abstract: Let S be a decomposition of a simple 4-regular plane graph into edge-disjoint cycles such that every two adjacent edges on a face belong to different cycles of S. Such graphs, called Gr¨ otzsch–Sachs graphs, may be considered as a result of a superposition of simple closed curves in the plane with tangencies disallowed. Koester studied the coloring of Gr¨otzschSachs graphs when all curves are circles. In 1984, he presented the first example of a 4-chromatic edge critical plane graph of order 40 formed by 7 circles. In the present paper, a new 4-chromatic edge critical graph generated by circles in the plane is presented.
Cite: Dobrynin A.A.
A new 4-chromatic edge critical Koester graph
Discrete Mathematics Letters. 2023. V.12. P.6-10. DOI: 10.47443/dml.2022.166 WOS Scopus OpenAlex
Dates:
Submitted: Jan 25, 2023
Accepted: Feb 13, 2023
Published print: Mar 7, 2023
Published online: Mar 7, 2023
Identifiers:
Web of science: WOS:001065538700002
Scopus: 2-s2.0-85176583730
OpenAlex: W4323352235
Citing:
DB Citing
OpenAlex 1
Web of science 2
Scopus 1
Altmetrics: