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: [email protected] (G. Gutin), [email protected] (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
SN - 0012-365X
VL - 213
SP - 153
EP - 161
JO - Discrete Mathematics
JF - Discrete Mathematics
IS - 1-3
T2 - Selected Topics in Discrete Mathematics
Y2 - 26 August 1996 through 28 September 1996
ER -