On monochromatic component size for improper colourings

DOI10.1016/j.dam.2004.10.005zbMath1060.05031OpenAlexW2066348861MaRDI QIDQ1775062

Keith J. Edwards, Graham E. Farr

Publication date: 4 May 2005

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2004.10.005

zbMATH Keywords

AlgorithmGraph colouringGraph partitionMetacolouringMonochromatic components

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On linear k-arboricity
• Two-coloring the edges of a cubic graph such that each monochromatic component is a path of length at most 5
• Relaxed chromatic numbers of graphs
• Relaxed coloring of a graph
• Bounded size components -- partitions and transversals.
• Partitioning into graphs with only small components
• Fragmentability of graphs
• Computational complexity of \((2,2)\) path chromatic number problem
• The strong chromatic number of a graph
• Path chromatic numbers of graphs
• Low-degree Graph Partitioning via Local Search with Applications to Constraint Satisfaction, Max Cut, and Coloring
• COVERING AND PACKING IN GRAPHS, I.