On color critical graphs
type: Item
instance of: scholarly article
title: On color critical graphs
zbMATH Open document ID: 0566.05030
DOI: 10.1016/0095-8956(85)90066-8
author: Vojtěch Rödl
author: Zsolt Tuza
published in: Journal of Combinatorial Theory. Series B
publication date: 1985-01-01T00:00:00Z
review text: The graph G is said to be \((k+1)\)-critical if its chromatic number is \(k+1\) but the chromatic number of every proper subgraph G' of G (i.e., E(G')\(\subset E(G))\) is \(\leq k\). In this paper it is proved that the minimal number of edges which have to be omitted from a \((k+1)\)-critical graph on n vertices in order to make it bipartite is at least \(\left( \begin{matrix} k\\ 2\end{matrix} \right)\) for n large enough and for every n there exists a \((k+1)\)-critical graph G, \(| V(G)| >n\) which can be made bipartite by the omission of \(\left( \begin{matrix} k\\ 2\end{matrix} \right)\) edges. Also, it is shown the existence of a function f(k,p) such that for any n there is a \((k+1)\)-critical graph with more than n vertices, girth greater than p which can be made bipartite by the omission of \(\leq f(k,p)\) edges. The authors investigate some other similar questions: critical graphs with a very long induced path and chromatic graphs satisfying symmetry properties (e.g., graphs with transitive automorphism group).
reviewed by: Ioan Tomescu
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 05C35
zbMATH DE Number: 3902683
zbMATH Keywords: bipartite graph
zbMATH Keywords: Turán's theorem
zbMATH Keywords: omission of edges
zbMATH Keywords: critical graph
zbMATH Keywords: girth
zbMATH Keywords: transitive automorphism group
MaRDI profile type: Publication
full work available at URL: 0095-8956(85)90066-8
OpenAlex ID: W2092384805
cites work: Q3852212
cites work: On the combinatorial problems which I would most like to see solved
cites work: Q4065548
cites work: Q4770982
cites work: Ensembles d'articulation d'un graphe \(\gamma\)-critique
cites work: Q4103565
cites work: Q4094883
cites work: Q5557742
description: scientific article; zbMATH DE number 3902683