No CrossRef data available.
Article contents
Improper colouring of graphs with no odd clique minor
Part of:
Graph theory
Published online by Cambridge University Press: 04 February 2019
Abstract
Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.
As a strengthening of Hadwiger’s conjecture, Gerards and Seymour conjectured that every graph with no odd Kt minor is (t − 1)-colourable. We prove two weaker variants of this conjecture. Firstly, we show that for each t ⩾ 2, every graph with no odd Kt minor has a partition of its vertex set into 6t − 9 sets V1, …, V6t−9 such that each Vi induces a subgraph of bounded maximum degree. Secondly, we prove that for each t ⩾ 2, every graph with no odd Kt minor has a partition of its vertex set into 10t −13 sets V1,…, V10t−13 such that each Vi induces a subgraph with components of bounded size. The second theorem improves a result of Kawarabayashi (2008), which states that the vertex set can be partitioned into 496t such sets.
MSC classification
Secondary:
05C83: Graph minors
Information
- Type
- Paper
- Information
- Copyright
- © Cambridge University Press 2019
Footnotes
†
The first author was supported by a TJ Park Science Fellowship of POSCO TJ Park Foundation.
‡
Supported by the National Research Foundation of Korea (NRF) grant funded by the Korean government (MSIT) (no. NRF-2017R1A2B4005020).
References
Bollobás, B. and Thomason, A. (1998) Proof of a conjecture of Mader, Erdős and Hajnal on topological complete subgraphs. European J. Combin. 19 883–887.CrossRefGoogle Scholar
Catlin, P. A. (1979) Hajós’ graph-coloring conjecture: variations and counterexamples. J. Combin. Theory Ser. B 26 268–274.CrossRefGoogle Scholar
Cowen, L., Goddard, W. and Jesurum, C. E. (1997) Defective coloring revisited. J. Graph Theory 24 205–219.3.0.CO;2-T>CrossRefGoogle Scholar
Diestel, R. (2010) Graph Theory, fourth edition, Vol. 173 of Graduate Texts in Mathematics, Springer.CrossRefGoogle Scholar
Dvořák, Z. and Norin, S. (2017) Islands in minor-closed classes, I: Bounded treewidth and separators. arXiv:1710.02727
Google Scholar
Edwards, K., Kang, D. Y., Kim, J., Oum, S. and Seymour, P. (2015) A relative of Hadwiger’s conjecture. SIAM J. Discrete Math. 29 2385–2388.CrossRefGoogle Scholar
Esperet, L. and Joret, G. (2014) Colouring planar graphs with three colours and no large monochromatic components. Combin. Probab. Comput. 23 551–570.CrossRefGoogle Scholar
Geelen, J., Gerards, B., Reed, B., Seymour, P. and Vetta, A. (2009) On the odd-minor variant of Hadwiger’s conjecture. J. Combin. Theory Ser. B 99 20–29.CrossRefGoogle Scholar
Geelen, J. and Huynh, T. (2004) Colouring graphs with no odd-Kn
minor. Manuscript. http://www.math.uwaterloo.ca/~jfgeelen/Publications/colour.pdf
Google Scholar
Guenin, B. (2005) Odd-K5-free graphs are 4-colourable. In Oberwolfach Report no. 3/2005, pp. 176–178. https://www.mfo.de/document/0503/OWR_2005_03.pdf
Google Scholar
Hadwiger, H. (1943) Über eine Klassifikation der Streckenkomplexe. Vierteljschr. Naturforsch. Ges. Zürich 88 133–142.Google Scholar
Harary, F. (1953–1954) On the notion of balance of a signed graph. Michigan Math. J. 2 143–146.Google Scholar
van den Heuvel, J. and Wood, D. R. (2018) Improper colourings inspired by Hadwiger’s conjecture. J. London Math. Soc. 98 129–148.CrossRefGoogle Scholar
Huynh, T., Oum, S. and Verdian-Rizi, M. (2017) Even-cycle decompositions of graphs with no odd-K4-minor. European J. Combin. 65 1–14.CrossRefGoogle Scholar
Kang, R. J. (2013) Improper choosability and Property B. J. Graph Theory 73 342–353.CrossRefGoogle Scholar
Kawarabayashi, K.-I. (2008) A weakening of the odd Hadwiger’s conjecture. Combin. Probab. Comput. 17 815–821.CrossRefGoogle Scholar
Kawarabayashi, K.-I. andMohar, B. (2007) A relaxed Hadwiger’s conjecture for list colorings. J. Combin. Theory Ser. B 97 647–651.CrossRefGoogle Scholar
Komlós, J. and Szemerédi, E. (1996) Topological cliques in graphs, II. Combin. Probab. Comput. 5 79–90.CrossRefGoogle Scholar
Kostochka, A. V. (1982) The minimum Hadwiger number for graphs with a given mean degree of vertices. Metody Diskret. Analiz. 38 37–58.Google Scholar
Kostochka, A. V. (1984) Lower bound of the Hadwiger number of graphs by their average degree. Combinatorica 4 307–316.CrossRefGoogle Scholar
Liu, C.-H. andOum, S. (2018) Partitioning H-minor free graphs into three subgraphs with no large components. J. Combin. Theory Ser. B 128 114–133.CrossRefGoogle Scholar
Mohar, B., Reed, B. and Wood, D. R. (2017) Colourings with bounded monochromatic components in graphs of given circumference. Australas. J. Combin. 69 236–242.Google Scholar
Norin, S., Scott, A., Seymour, P. andWood, D. R. (2017) Clustered colouring in minor-closed classes. arXiv:1708.02370
Google Scholar
Ossona de Mendez, P., Oum, S. andWood, D. R. (2018) Defective colouring of graphs excluding a subgraph or minor. Combinatorica. doi: https://doi.org/10.1007/s00493-018-3733-1.CrossRefGoogle Scholar
Robertson, N., Seymour, P. and Thomas, R. (1993) Hadwiger’s conjecture for K6-free graphs. Combinatorica 13 279–361.CrossRefGoogle Scholar
Seymour, P. (2016) Hadwiger’s conjecture. In Open Problems in Mathematics (Nash, J. and Rassias, M., eds), Springer.Google Scholar
Thomason, A. (1984) An extremal function for contractions of graphs. Math. Proc. Cambridge Philos. Soc. 95 261–265.CrossRefGoogle Scholar
Thomason, A. (2001) The extremal function for complete minors. J. Combin. Theory Ser. B 81 318–338.CrossRefGoogle Scholar
Wood, D. R. (2010) Contractibility and the Hadwiger conjecture. European J. Combin. 31 2102–2109.CrossRefGoogle Scholar
Wood, D. R. (2018) Defective and clustered graph colouring. Electron. J. Combin. #DS23.Google Scholar
You have
Access
- 10
- Cited by