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

MaRDI QIDQ311567zbMATH OpenFDO

Authors Jeno Lehel, András Gyárfás

Publication date 13 September 2016

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

Full work available at URL https://arxiv.org/abs/1509.03408, http://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i3p40

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

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)

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.

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

Cites work

• A linear-time algorithm for testing the truth of certain quantified Boolean formulas
• Cliques in the union of graphs
• Covering a hypergraph of subgraphs
• scientific article; zbMATH DE number 3632548 (Why is no real title available?)
• scientific article; zbMATH DE number 3332242 (Why is no real title available?)
• Intersection properties of families of convex (n,d)-bodies
• KKM -- a topological approach for trees
• Lower bounds on the transversal numbers of \(d\)-intervals
• Piercing d-intervals
• Transversals of d-intervals
• Transversals of 2-intervals, a topological approach

Cited in

(1)

• Clique covers of complete graphs and piercing multitrack 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)