Hostname: page-component-586b7cd67f-2plfb Total loading time: 0 Render date: 2024-11-30T23:12:45.691Z Has data issue: false hasContentIssue false
  • English
  • Français

Improper colouring of graphs with no odd clique minor

Part of: Graph theory

Published online by Cambridge University Press:  04 February 2019

Dong Yeap Kang  and
Sang-Il Oum
Dong Yeap Kang
Affiliation:
Department of Mathematical Sciences, KAIST, 291 Daehak-ro Yuseong-gu Daejeon, 34141South Korea
Sang-Il Oum*
Affiliation:
Department of Mathematical Sciences, KAIST, 291 Daehak-ro Yuseong-gu Daejeon, 34141South Korea Discrete Mathematics Group, Institute for Basic Science (IBS), 55 Expo-ro Yuseong-gu Daejeon, 34126South Korea
*
*Corresponding author. Email: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

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

Primary: 05C15: Coloring of graphs and hypergraphs
Secondary: 05C83: Graph minors
Type
Paper
Information
Combinatorics, Probability and Computing , Volume 28 , Issue 5 , September 2019 , pp. 740 - 754
Copyright
© Cambridge University Press 2019 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

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
Jensen, T. R. and Toft, B. (1995) Graph Coloring Problems, Wiley.Google 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