TY - JOUR

T1 - On the Hajós number of graphs

AU - Gutin, G.

AU - Kostochka, A. V.

AU - Toft, B.

N1 - Funding Information:
∗Corresponding author. E-mail addresses: z.g.gutin@brunel.ac.uk (G. Gutin), sasha@math.nsc.ru (A.V. Kostochka), btoft@imada. sdu.dk (B. Toft) 1This work was partially supported by the grant for discrete mathematics of the Danish Natural Science Research Council. 2This author nished his part of work during his stay at SFB343 ‘Diskrete Strukturen in der Mathematik’ of Bielefeld University. His work was also partially supported by the grant 96-01-01614 of the Russian Foundation for Fundamental Research. 3This work was partially supported by the grant for discrete mathematics of the Danish Natural Science Research Council.

PY - 2000/2/28

Y1 - 2000/2/28

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=0041780887&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0041780887&partnerID=8YFLogxK

U2 - 10.1016/S0012-365X(99)00175-2

DO - 10.1016/S0012-365X(99)00175-2

M3 - Conference article

AN - SCOPUS:0041780887

VL - 213

SP - 153

EP - 161

JO - Discrete Mathematics

JF - Discrete Mathematics

SN - 0012-365X

IS - 1-3

T2 - Selected Topics in Discrete Mathematics

Y2 - 26 August 1996 through 28 September 1996

ER -