Hostname: page-component-74656f9884-j7cmm Total loading time: 0 Render date: 2026-11-07T04:08:32.418Z Has data issue: false hasContentIssue false
  • English
  • Français

Graph Colouring with No Large Monochromatic Components

Published online by Cambridge University Press:  01 July 2008

NATHAN LINIAL ,
JIŘÍ MATOUŠEK ,
OR SHEFFET  and
GÁBOR TARDOS
NATHAN LINIAL
Affiliation:
School of Computer Science and Engineering, Hebrew University, Jerusalem, Israel (e-mail: nati@cs.huji.ac.il; or.sheffet@gmail.com)
JIŘÍ MATOUŠEK
Affiliation:
Department of Applied Mathematics and Institute of Theoretical Computer Science (ITI), Charles University, Malostranské nám. 25, 118 00 Praha 1, Czech Republic (e-mail: matousek@kam.mff.cuni.cz)
OR SHEFFET
Affiliation:
School of Computer Science and Engineering, Hebrew University, Jerusalem, Israel (e-mail: nati@cs.huji.ac.il; or.sheffet@gmail.com)
GÁBOR TARDOS
Affiliation:
School of Computing Science, Simon Fraser University, Burnaby, BC, Canada and Rényi Institute, Budapest, Hungary (e-mail: tardos@cs.sfu.ca)
Rights & Permissions [Opens in a new window]

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.

For a graph G and an integer t we let mcct(G) be the smallest m such that there exists a colouring of the vertices of G by t colours with no monochromatic connected subgraph having more than m vertices. Let be any non-trivial minor-closed family of graphs. We show that mcc2(G) = O(n2/3) for any n-vertex graph G ∈ . This bound is asymptotically optimal and it is attained for planar graphs. More generally, for every such , and every fixed t we show that mcct(G)=O(n2/(t+1)). On the other hand, we have examples of graphs G with no Kt+3 minor and with mcct(G)=Ω(n2/(2t−1)).

It is also interesting to consider graphs of bounded degrees. Haxell, Szabó and Tardos proved mcc2(G) ≤ 20000 for every graph G of maximum degree 5. We show that there are n-vertex 7-regular graphs G with mcc2(G)=Ω(n), and more sharply, for every ϵ > 0 there exists cϵ > 0 and n-vertex graphs of maximum degree 7, average degree at most 6 + ϵ for all subgraphs, and with mcc2(G) ≥ cϵn. For 6-regular graphs it is known only that the maximum order of magnitude of mcc2 is between $\sqrt n$ and n.

We also offer a Ramsey-theoretic perspective of the quantity mcct(G).

Information

Type
Paper
Information
Combinatorics, Probability and Computing , Volume 17 , Issue 4 , July 2008 , pp. 577 - 589
Copyright
Copyright © Cambridge University Press 2008

References

[1]Alon, N., Ding, G., Oporowski, B. and Vertigan, D. (2003) Partitioning into graphs with only small components. J. Combin. Theory Ser. B 87 231–243.Google Scholar
[2]Alon, N., Seymour, P. and Thomas, R. (1990) A separator theorem for nonplanar graphs. J. Amer. Math. Soc. 3,4 801–808.CrossRefGoogle Scholar
[3]Berke, R. (2008) Coloring and transversals of graphs. PhD thesis, ETH Zurich.Google Scholar
[4]Berke, R. and Szabó, T. (2005) Relaxed two-coloring of cubic graphs. In DMTCS Proc. 2005 European Conference on Combinatorics, Graph Theory and Applications (EUROCOMB), pp. 341–344.Google Scholar
[5]Bollobás, B. (1986) Set Systems, Hypergraphs, Families of Vectors and Combinatorial Probability, Cambridge University Press.Google Scholar
[6]Bollobás, B. and Leader, I. (1991) Edge-isoperimetric inequalities in the grid. Combinatorica 11 299–314.Google Scholar
[7]Ding, G., Oporowski, B., Sanders, D. and Vertigan, D. (1996) Preprint, Louisiana State University, Baton Rouge.Google Scholar
[8]Gale, D. (1979) The game of hex and the Brouwer fixed-point theorem. Amer. Math. Monthly 86 818–827.CrossRefGoogle Scholar
[9]Haxell, P., Szabó, T. and Tardos, G. (2003) Bounded size components: Partitions and transversals. J. Combin. Theory Ser. B 88 281–297.CrossRefGoogle Scholar
[10]Hoory, S., Linial, N. and Wigderson, A. (2006) Expander graphs and their applications. Bull. Amer. Math. Soc. 43,4 439–561.CrossRefGoogle Scholar
[11]Jackson, B. and Wormald, N. (1996) On the linear k-arboricity of cubic graphs. Discrete Math. 162 293–297.CrossRefGoogle Scholar
[12]Janson, S., Łuczak, T. and Ruciński, A. (2000) Topics in Random Graphs, Wiley.CrossRefGoogle Scholar
[13]Jensen, T. R. and Toft, B. (1995) Graph Coloring Problems, Wiley–Interscience Series in Discrete Mathematics and Optimization.Google Scholar
[14]Kawarabayashi, K. and Mohar, B. (2007) A relaxed Hadwiger's conjecture for list colorings. J. Combin. Theory Ser. B 97 647–651.CrossRefGoogle Scholar
[15]Kleinberg, J., Motwani, R., Raghavan, P. and Venkatasubramanian, S. (1997) Storage management for evolving databases. In Proc. 38th IEEE Symposium on Foundations of Computer Science (FOCS), pp. 353–362.Google Scholar
[16]Linial, N. and Saks, M. (1993) Low diameter graph decompositions. Combinatorica 13 441–454.CrossRefGoogle Scholar
[17]Lipton, R. and Tarjan, R. (1979) A separator theorem for planar graphs. SIAM J. Appl. Math. 2 177–190.Google Scholar
[18]Matoušek, J. and Nešetřil, J. (1998) Invitation to Discrete Mathematics, Oxford University Press.CrossRefGoogle Scholar
[19]Matoušek, J. and Přívětivý, A. Large monochromatic components in two-colored grids. SIAM J. Discrete Math., in press.Google Scholar
[20]Reed, B. (1992) Finding approximate separators and computing tree width quickly. In Proc. 24th Annual ACM Symposium on the Theory of Computing (STOC), pp. 221–228.Google Scholar
[21]Robertson, N. and Seymour, P. (1986) Graph minors II: Algorithmic aspects of tree-width. J. Algorithms 7 309–322.CrossRefGoogle Scholar
[22]Robertson, N. and Seymour, P. (1991) Graph minors X: Obstructions to tree-decomposition. J. Combin. Theory Ser. B 52 153–190.CrossRefGoogle Scholar
[23]Robertson, N. and Seymour, P. (1995) Graph minors XIII: The disjoint path problem. J. Combin. Theory Ser. B 63 65–110.Google Scholar
[24]Thomassen, C. (1999) Two-colouring the edges of a cubic graph such that each monochromatic component is a path of length at most 5. J. Combin. Theory Ser. B 75 100–109.Google Scholar