Bounded size components -- partitions and transversals.

DOI10.1016/S0095-8956(03)00031-5zbMath1033.05083OpenAlexW1986861105MaRDI QIDQ1400964

Tibor Szabó, Gábor Tardos, Penny E. Haxell

Publication date: 17 August 2003

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

Full work available at URL: https://doi.org/10.1016/s0095-8956(03)00031-5

zbMATH Keywords

bounded size componentspartition of vertex settransveral

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Related Items

Clustered colouring of graph classes with bounded treedepth or pathwidth ⋮ Clustered 3-colouring graphs of bounded degree ⋮ Bounded transversals in multipartite graphs ⋮ Clustered variants of Hajós' conjecture ⋮ Colouring planar graphs with bounded monochromatic components ⋮ Relaxed two-coloring of cubic graphs ⋮ Strong coloring 2‐regular graphs: Cycle restrictions and partial colorings ⋮ Large Monochromatic Components in Two-colored Grids ⋮ Graph coloring with no large monochromatic components ⋮ Colorful strips ⋮ On generalized choice and coloring numbers ⋮ Deciding Relaxed Two-Colourability: A Hardness Jump ⋮ Isomorphic bisections of cubic graphs ⋮ A note on 2-bisections of claw-free cubic graphs ⋮ Islands in Graphs on Surfaces ⋮ On monochromatic component size for improper colourings ⋮ Acyclic systems of representatives and acyclic colorings of digraphs ⋮ 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 ⋮ 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

• On linear k-arboricity
• On complete subgraphs of \(r\)-chromatic graphs
• Two-coloring the edges of a cubic graph such that each monochromatic component is a path of length at most 5
• On the linear \(k\)-arboricity of cubic graphs
• Independent transversals in \(r\)-partite graphs
• Partitioning into graphs with only small components
• A Note on Vertex List Colouring
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item