×

On vertex partitions and some minor-monotone graph parameters. (English) Zbl 1222.05211

Summary: We study vertex partitions of graphs according to some minor-monotone graph parameters. G. Ding, B. Oporowski, D. P. Sanders and D. Vertigan [J. Comb. Theory, Ser. B 79, No.2, 221–246 (2000; Zbl 1029.05041)] proved that some minor-monotone parameters \(\rho \) are such that, any graph G with \(\rho (G) \geq 2\) admits a vertex partition into two graphs with parameter \(\rho \) at most \(\rho (G) - 1\). Here we prove that some of these parameters \(\rho \) are such that, any graph G with \(\rho (G) \geq 3\) admits a vertex partition into three graphs with parameter \(\rho \) at most \(\rho (G) - 2\).

MSC:

05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)

Citations:

Zbl 1029.05041
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Akiyama, Path chromatic numbers of graphs, J Graph Theory 13 pp 569– (1989) · Zbl 0688.05024
[2] Broere, Graph Theory with Applications to Algorithms and Computer Science pp 151– (1985)
[3] Chartrand, Graphs with forbidden subgraphs, J Combin Theory Ser B 10 pp 12– (1971) · Zbl 0223.05101
[4] Colin de Verdière, Sur un nouvel invariant des graphes et un critère de planarité, J Combin Theory Ser B 50 (1) pp 11– (1990) · Zbl 0742.05061
[5] Colin de Verdière, On a new graph invariant and a criterion for planarity, Contemp Math 147 pp 137– (1993) · Zbl 0791.05024 · doi:10.1090/conm/147/01168
[6] Ding, Partitioning graphs of bounded tree-width, Combinatorica 18 (1) pp 1– (1998) · Zbl 0924.05022
[7] Ding, Surfaces, tree-width, clique-minors, and partitions, J Combin Theory Ser B 79 (2) pp 221– (2000) · Zbl 1029.05041
[8] Goddard, Acyclic colorings of planar graphs, Discrete Math 91 pp 91– (1991) · Zbl 0742.05041
[9] Hanson, The (m, n)-conjecture is false, Bull Inst Combin Appl 11 pp 59– (1994) · Zbl 0813.05026
[10] van der Holst, On a minor-monotone graph invariant, J Combin Theory Ser B 65 (2) pp 291– (1995) · Zbl 0839.05034
[11] van der Holst, The Colin de Verdière graph parameter, Bolyai Soc Math Stud 7 pp 29– (1999) · Zbl 0930.05065
[12] van der Holst, On a graph property generalizing planarity and flatness, Combinatorica 29 pp 337– (2009)
[13] Jørgensen, Some probabilistic and extremal results on subdivisions and odd subdivisions of graphs, J Graph Theory 13 (1) pp 75– (1989) · Zbl 0672.05070
[14] Jørgensen, Contractions to K8, J Graph Theory 18 (5) pp 431– (1994)
[15] Kawarabayashi, Any 7-chromatic graph has K7 or K4, 4 as a minor, Combinatorica 25 (3) pp 327– (2005)
[16] Mader, Homomorphiesätze für Graphen (German), Math Ann 178 pp 154– (1968) · Zbl 0165.57401
[17] Mihók, Graphs and Other Combinatorial Topics pp 183– (1983)
[18] Poh, On the linear vertex-arboricity of a planar graph, J Graph Theory 14 (1) pp 73– (1990) · Zbl 0705.05016
[19] Robertson, Hadwiger’s conjecture for K6-free graphs, Cominatorica 13 pp 3279– (1993)
[20] Woodall, Improper colourings of graphs, Pitman Res Notes Math Ser 218 pp 45– (1990) · Zbl 0693.05028
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.