No Detail Found!

A new 4-chromatic edge critical Koester graph

Author(s)
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.
Publication Details
Page(s) 6-10
Published Journal: Discrete Mathematics Letters, Volume: 12, Issue: 0, Year: 2023

Request the full text from PASTIC

Keywords
4-critical graph, Koester graph, plane graph, Gro¨tzsch-Sachs graph
0

Citations

0

Downloads

74

Views