Partition of Graphs and Hypergraphs into Monochromatic Connected Parts

  • Shinya Fujita
  • Michitaka Furuya
  • András Gyárfás
  • Ágnes Tóth
Keywords: Graph Theory


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.

Author Biographies

Shinya Fujita, Maebashi Institute of Technology
Department of Integrated Design Engineering
Michitaka Furuya, Tokyo University of Science
Department of Mathematical Information Science
András Gyárfás, Hungarian Academy of Sciences
Alfréd Rényi Institute of Mathematics
Ágnes Tóth, Budapest University of Technology and Economics
Department of Computer Science and Information Theory
Article Number