Red-blue clique partitions and (1-1)-transversals

zbMATH Open1344.05106arXiv1509.03408MaRDI QIDQ311567FDOQ311567

Jeno Lehel, András Gyárfás

Publication date: 13 September 2016

Published in: The Electronic Journal of Combinatorics (Search for Journal in Brave)

Abstract: Motivated by the problem of Gallai on $(1-1)$-transversals of $2$-intervals, it was proved by the authors in 1969 that if the edges of a complete graph $K$ are colored with red and blue (both colors can appear on an edge) so that there is no monochromatic induced $C_4$ and $C_5$ then the vertices of $K$ can be partitioned into a red and a blue clique. Aharoni, Berger, Chudnovsky and Ziani recently strengthened this by showing that it is enough to assume that there is no induced monochromatic $C_4$ and there is no induced $C_5$ in {em one of the colors}. Here this is strengthened further, it is enough to assume that there is no monochromatic induced $C_4$ and there is no $K_5$ on which both color classes induce a $C_5$. We also answer a question of Kaiser and Rabinovich, giving an example of six $2$-convex sets in the plane such that any three intersect but there is no $(1-1)$-transversal for them.

Full work available at URL: https://arxiv.org/abs/1509.03408

File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Recommendations

• On 2-colored graphs and partitions of boxes
• Clique-transversal sets of line graphs and complements of line graphs
• Clique-transversal sets and weak 2-colorings in graphs of small maximum degree
• Two-colorings with many monochromatic cliques in both colors
• On the partition and coloring of a graph by cliques

zbMATH Keywords

\((1-1)\)-transversalred-blue clique cover

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Transversal (matching) theory (05D15)

Cites Work

• A linear-time algorithm for testing the truth of certain quantified Boolean formulas
• Title not available (Why is that?)
• Intersection properties of families of convex \((n,d)\)-bodies
• Transversals of \(d\)-intervals
• Piercing \(d\)-intervals
• Transversals of 2-intervals, a topological approach
• Covering a hypergraph of subgraphs
• Cliques in the union of graphs
• KKM -- a topological approach for trees
• Title not available (Why is that?)
• Lower bounds on the transversal numbers of \(d\)-intervals

This page was built for publication: Red-blue clique partitions and \((1-1)\)-transversals

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q311567)