On nearly regular co-critical graphs
type: Item
instance of: scholarly article
title: On nearly regular co-critical graphs
zbMATH Open document ID: 0859.05061
DOI: 10.1016/0012-365X(95)00121-C
author: Tibor Szabó
published in: Discrete Mathematics
publication date: 1997-04-07T00:00:00Z
review text: A graph \(G\) is \((K_3,K_3)\)-co-critical if the edges of \(G\) can be coloured with two colours without obtaining a monochromatic triangle, but adding any new edge to the graph, this kind of ``good'' colouring is impossible. The question is how small the maximum degree \(\Delta\) of a \((K_3,K_3)\)-co-critical graph can be. It is shown that \(\Delta= O(n^{3/4})\) by a simple constructive example. Still there is a considerable gap between the trivial lower bound \(c\sqrt n\) for \(\Delta\) and this upper bound.
Mathematics Subject Classification ID: 05C55
zbMATH DE Number: 955165
zbMATH Keywords: co-critical graphs
zbMATH Keywords: anti-Ramsey theory
zbMATH Keywords: monochromatic triangle
reviewed by: G. Gutin
MaRDI profile type: Publication
cites work: Maximal triangle‐free graphs with restrictions on the degrees
cites work: Q4871067
description: scientific article; zbMATH DE number 955165