Partition of graphs and hypergraphs into monochromatic connected parts
type: Item
instance of: scholarly article
title: Partition of graphs and hypergraphs into monochromatic connected parts
zbMATH Open document ID: 1252.05176
author: Shinya Fujita
author: Michitaka Furuya
author: András Gyárfás
author: Ágnes Tóth
published in: The Electronic Journal of Combinatorics
publication date: 2012-10-24T00:00:00Z
full work available at URL: v19i3p27
review text: Summary: We show that two results on covering of edge colored graphs by monochromatic connected parts can be extended to partitioning. We prove that for any 2-edge-colored non-trivial \(r\)-uniform hypergraph \(H\), the vertex set can be partitioned into at most \(\alpha (H)-r+2\) monochromatic connected parts, where \(\alpha (H)\) is the maximum number of vertices that does not contain any edge. In particular, any 2-edge-colored graph \(G\) can be partitioned into \(\alpha(G)\) monochromatic connected parts, where \(\alpha (G)\) denotes the independence number of \(G\). This extends König's theorem, a special case of Ryser's conjecture. Our second result is about Gallai-colorings, i.e. edge-colorings of graphs without 3-edge-colored triangles. We show that for any Gallai-coloring of a graph \(G\), the vertex set of \(G\) can be partitioned into monochromatic connected parts, where the number of parts depends only on \(\alpha(G)\). This extends its cover-version proved earlier by Simonyi and two of the authors.
Mathematics Subject Classification ID: 05C70
Mathematics Subject Classification ID: 05C15
zbMATH DE Number: 6098369
zbMATH Keywords: covering of edge colored graphs by monochromatic connected parts
MaRDI profile type: Publication
description: scientific article; zbMATH DE number 6098369