Graph coloring with no large monochromatic components

DOI10.1016/j.endm.2007.07.020zbMath1341.05080arXivmath/0703362OpenAlexW2066530434MaRDI QIDQ3503460

Nathan Linial, Or Sheffet, Gábor Tardos, Ji{ří} Matoušek

Publication date: 5 June 2008

Published in: Electronic Notes in Discrete Mathematics, Combinatorics, Probability and Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/math/0703362

zbMATH Keywords

minor-closed family of graphsgraph colouringgraph minorsmonochromatic connected subgraphs

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Coloring of graphs and hypergraphs (05C15) Graph minors (05C83) Generalized Ramsey theory (05C55) Ramsey theory (05D10)

Related Items

Clustered 3-colouring graphs of bounded degree, Harary polynomials, Clustered variants of Hajós' conjecture, Colouring planar graphs with bounded monochromatic components, Large Monochromatic Components in Two-colored Grids, Information-sharing in social networks, Isomorphic bisections of cubic graphs, On the complexity of generalized chromatic polynomials, A note on 2-bisections of claw-free cubic graphs, Islands in Graphs on Surfaces, Connection Matrices for MSOL-Definable Structural Invariants, On the \(k\)-component independence number of a tree, Splitting Planar Graphs of Girth 6 into Two Linear Forests with Short Paths, Immersion and clustered coloring

Cites Work

• Unnamed Item
• A relaxed Hadwiger's conjecture for list colorings
• Graph minors. X: Obstructions to tree-decomposition
• Edge-isoperimetric inequalities in the grid
• Two-coloring the edges of a cubic graph such that each monochromatic component is a path of length at most 5
• Low diameter graph decompositions
• On the linear \(k\)-arboricity of cubic graphs
• Bounded size components -- partitions and transversals.
• Partitioning into graphs with only small components
• Graph minors. XIII: The disjoint paths problem
• Large Monochromatic Components in Two-colored Grids
• Expander graphs and their applications
• Graph minors. II. Algorithmic aspects of tree-width
• A Separator Theorem for Planar Graphs
• The Game of Hex and the Brouwer Fixed-Point Theorem
• A Separator Theorem for Nonplanar Graphs