Partitioning into graphs with only small components

DOI10.1016/S0095-8956(02)00006-0zbMath1023.05045MaRDI QIDQ1405114

Guoli Ding, Bogdan Oporowski, Dirk Vertigan, Noga Alon

Publication date: 25 August 2003

Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

zbMATH Keywords

graph coloringvertex partitiontree-widthedge partition

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Coloring of graphs and hypergraphs (05C15)

Related Items (43)

Degree Ramsey Numbers of Graphs ⋮ Clustered colouring of graph classes with bounded treedepth or pathwidth ⋮ Clustered 3-colouring graphs of bounded degree ⋮ A Relative of Hadwiger's Conjecture ⋮ Coloring subgraphs with restricted amounts of hues ⋮ Clustered variants of Hajós' conjecture ⋮ Colouring planar graphs with bounded monochromatic components ⋮ Relaxed two-coloring of cubic graphs ⋮ Partitioning sparse graphs into an independent set and a graph with bounded size components ⋮ Path partition of planar graphs with girth at least six ⋮ Large Monochromatic Components in Two-colored Grids ⋮ Graph coloring with no large monochromatic components ⋮ Bounded size components -- partitions and transversals. ⋮ Partitioning into graphs with only small components ⋮ Information-sharing in social networks ⋮ From the plane to higher surfaces ⋮ Partitioning \(H\)-minor free graphs into three subgraphs with no large components ⋮ Unnamed Item ⋮ On the minimum monochromatic or multicolored subgraph partition problems ⋮ On generalized choice and coloring numbers ⋮ Degree bipartite Ramsey numbers ⋮ Deciding Relaxed Two-Colourability: A Hardness Jump ⋮ Product structure of graph classes with bounded treewidth ⋮ Isomorphic bisections of cubic graphs ⋮ Partitioning \(H\)-minor free graphs into three subgraphs with no large components ⋮ On the complexity of generalized chromatic polynomials ⋮ A note on 2-bisections of claw-free cubic graphs ⋮ Islands in Graphs on Surfaces ⋮ On monochromatic component size for improper colourings ⋮ A lower bound on the multicolor size-Ramsey numbers of paths in hypergraphs ⋮ Asymptotic dimension of minor-closed families and Assouad-Nagata dimension of surfaces ⋮ Clustered coloring of graphs with bounded layered treewidth and bounded degree ⋮ Colouring strong products ⋮ Tree-partitions with bounded degree trees ⋮ On the \(k\)-component independence number of a tree ⋮ Defective and clustered choosability of sparse graphs ⋮ Splitting Planar Graphs of Girth 6 into Two Linear Forests with Short Paths ⋮ On tree-partition-width ⋮ Hadwiger’s Conjecture ⋮ Finding independent transversals efficiently ⋮ Colouring Planar Graphs With Three Colours and No Large Monochromatic Components ⋮ Some of My Favorite Coloring Problems for Graphs and Digraphs ⋮ Immersion and clustered coloring

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• The linear arboricity of graphs
• Two-coloring the edges of a cubic graph such that each monochromatic component is a path of length at most 5
• Partitioning into graphs with only small components
• Excluding any graph as a minor allows a low tree-width 2-coloring
• On the bandwidth of triangulated triangles
• On tree-partitions of graphs
• Linear arboricity and linear \(k\)-arboricity of regular graphs

This page was built for publication: Partitioning into graphs with only small components