On the Hajós number of graphs (Q1970708)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On the Hajós number of graphs |
scientific article |
Statements
On the Hajós number of graphs (English)
0 references
27 September 2000
0 references
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.\)
0 references
Hajós number
0 references