Partition of graphs and hypergraphs into monochromatic connected parts

Shinya Fujita¹ ; Michitaka Furuya² ; András Gyárfás³ ; Ágnes Tóth⁴

¹Maebashi Institute of Technology
²Tokyo University of Science
³Hungarian Academy of Sciences
⁴Budapest University of Technology and Economics

The electronic journal of combinatorics, Tome 19 (2012) no. 3

Résumé

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.

Détail

DOI : 10.37236/2121

Classification : 05C70, 05C15
Mots-clés : covering of edge colored graphs by monochromatic connected parts