Author(s):
1. Andrey A. Dobrynin:
Sobolev Institute of Mathematics, Siberian Branch of the Russian Academy of Sciences,Novosibirsk 630090,Russia
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 Gro¨tzsch-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 Gro¨tzschSachs 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.
Page(s):
6-10
Published:
Journal: Discrete Mathematics Letters, Volume: 12, Issue: 0, Year: 2023
Keywords:
4critical graph
,
Koester graph
,
plane graph
,
Gro¨tzschSachs graph
References:
References are not available for this document.
Citations
Citations are not available for this document.