Two graphs on the same vertex set form a cross-intersecting couple if they have a pair of clique coverings with the property that every pair of cliques from the respective coverings intersect. In particular, a graph is called normal if it forms a cross-intersecting couple with its complement. We determine the largest size of families of graphs every pair of which forms a cross-intersecting couple under various additional restrictions. (C) 2007 Wiley Periodicals, Inc.
Cross-intersecting couples of graphs / Fachini, Emanuela; Korner, Janos. - In: JOURNAL OF GRAPH THEORY. - ISSN 0364-9024. - STAMPA. - 56:2(2007), pp. 105-112. [10.1002/jgt.20252]
Cross-intersecting couples of graphs
FACHINI, Emanuela;KORNER, JANOS
2007
Abstract
Two graphs on the same vertex set form a cross-intersecting couple if they have a pair of clique coverings with the property that every pair of cliques from the respective coverings intersect. In particular, a graph is called normal if it forms a cross-intersecting couple with its complement. We determine the largest size of families of graphs every pair of which forms a cross-intersecting couple under various additional restrictions. (C) 2007 Wiley Periodicals, Inc.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
