On the Hajós number of graphs

G. Gutin, A. V. Kostochka, B. Toft

Research output: Contribution to journalConference articlepeer-review


A graph G is said to have property Pm if it contains no subdivision of Km+1 and no subdivision of K⌈m/2⌉+1,⌊m/2⌋+1. Chartrand et al. (J. Combin Theory 10 (1971) 12-41) (see also Problem 6.3 in Jensen and Toft (Graph Coloring Problems, Wiley, New York, 1995) conjectured that the set of vertices (respectively, edges) of any graph with property Pm can be partitioned into m - n + 1 subsets such that each of these subsets induces a graph with property Pn, provided m≥n≥1 (respectively, m≥n≥2). We prove that both conjectures fail when m > cn2 for some positive constant c. In fact, we prove that under the condition m > cn2, there exists a graph G with property Pm such that in every colouring of its vertices or edges with m colours there is a monochromatic subgraph H with Hajós number h(H) > n, that is, with a subdivision of Kn+1. In addition, we prove bounds of Nordhaus-Gaddum type for the Hajós number.

Original languageEnglish (US)
Pages (from-to)153-161
Number of pages9
JournalDiscrete Mathematics
Issue number1-3
StatePublished - Feb 28 2000
Externally publishedYes
EventSelected Topics in Discrete Mathematics - Warsaw, Poland
Duration: Aug 26 1996Sep 28 1996

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics

Fingerprint Dive into the research topics of 'On the Hajós number of graphs'. Together they form a unique fingerprint.

Cite this