On the Hajós number of graphs
type: Item
instance of: scholarly article
title: On the Hajós number of graphs
zbMATH Open document ID: 0945.05020
DOI: 10.1016/S0012-365X(99)00175-2
author: G. Gutin
author: Alexandr Kostochka
author: Bjarne Toft
published in: Discrete Mathematics
publication date: 2000-09-27T00:00:00Z
review text: A graph \(G\) is said to have property \(P_m\) if it contains neither a subdivison of a complete graph \(K_{m+1}\) nor a subdivison of a complete bipartite graph \(K(\left\lfloor \frac m2\right\rfloor +1,\left\lceil \frac m2\right\rceil +1).\) \textit{G. Chartrand, D. Geller}, and \textit{S. Hedetniemi} [J. Comb. Theory, Ser. B 10, 12-41 (1971; Zbl 0223.05101)] conjectured that, for any \(n,m\) with \(m\geq n\geq 1\) \((m\geq n\geq 2)\), the set of vertices (edges) of any graph having the property \(P_m\) can be partitioned into \(m-n+1\) sets such that each of these sets induces a graph with property \(P_n.\) It is shown in the paper that there exists a positive constant \(c\) so that both conjectures fail for \(m>cn^2.\)
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 05C35
zbMATH DE Number: 1420382
zbMATH Keywords: Hajós number
reviewed by: Peter Horák
MaRDI profile type: Publication
full work available at URL: s0012-365x(99)00175-2
OpenAlex ID: W1985032817
Recommended article: On the Hosoya index of graphs
Recommended article: Q3807240
Recommended article: Q4949853
Recommended article: Q5750883
Recommended article: Q3701447
Recommended article: On the hull number of some graph classes
Recommended article: Hajós' conjecture and cycle power graphs
Recommended article: The Hadwiger number of complements of some graphs
Recommended article: Hajós' conjecture and projective graphs
description: scientific article; zbMATH DE number 1420382