Hostname: page-component-cd9895bd7-fscjk Total loading time: 0 Render date: 2024-12-25T18:40:58.126Z Has data issue: false hasContentIssue false
  • English
  • Français

Clique Partitions of Chordal Graphs†

Published online by Cambridge University Press:  12 September 2008

Paul Erdős ,
Edward T. Ordman  and
Yechezkel Zalcstein
Paul Erdős
Affiliation:
Mathematical Institute, Hungarian Academy of Sciences
Edward T. Ordman
Affiliation:
Memphis State University, Memphis, TN 38152, U.S.A.
Yechezkel Zalcstein
Affiliation:
Division of Computer and Computation Research, National Science Foundation Washington, D.C. 20550, U.S.A.
Get access Rights & Permissions [Opens in a new window]

Abstract

To partition the edges of a chordal graph on n vertices into cliques may require as many as n2/6 cliques; there is an example requiring this many, which is also a threshold graph and a split graph. It is unknown whether this many cliques will always suffice. We are able to show that (1 − c)n2/4 cliques will suffice for some c > 0.

Type
Research Article
Information
Combinatorics, Probability and Computing , Volume 2 , Issue 4 , December 1993 , pp. 409 - 415
Copyright
Copyright © Cambridge University Press 1993

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

[1]Bender, E. A., Richmond, L. B. and Wormald, N. C. (1985) Almost all chordal graphs split. J. Austral. Math. Soc. (A) 38 214–221.CrossRefGoogle Scholar
[2]Caccetta, L., Erdős, P., Ordman, E. and Pullman, N. (1985) The difference between the clique numbers of a graph. Ars Combinatoria 19 A 97–106.Google Scholar
[3]Chartrand, G. and Lesniak, L. (1986) Graphs and Digraphs, 2nd. Edition, Wadsworth, Belmont, CA.Google Scholar
[4]Chvátal, V. and Hammer, P. (1973) Set packing and threshold graphs, Univ. of Waterloo Research Report CORR 73–21.Google Scholar
[5]Chvátal, V. and Hammer, P. (1977) Aggregation of inequalities in integer programming. Ann. Discrete Math 1 145–162.CrossRefGoogle Scholar
[6]DeBruijn, N. G. and Erdős, P. (1948) On a combinatorial problem. Indag. Math. 10 421–423.Google Scholar
[7]Erdős, P., Faudree, R. and Ordman, E. (1988) Clique coverings and clique partitions. Discrete Mathematics 72 93–101.CrossRefGoogle Scholar
[8]Erdős, P., Goodman, A. W. and Posa, L. (1966) The representation of a graph by set intersections. Canad. J. Math. 18 106–112.CrossRefGoogle Scholar
[9]Erdős, P., Gyárfás, A., Ordman, E. T. and Zalcstein, Y. (1989) The size of chordal, interval, and threshold subgraphs. Combinatorica 9 (3) 245–253.CrossRefGoogle Scholar
[10]Golumbic, M. (1980) Algorithmic Graph Theory and Perfect Graphs, Academic Press, New York.Google Scholar
[11]Gregory, D. A. and Pullman, N. J. (1982) On a clique covering problem of Orlin. Discrete Math. 41 97–99.CrossRefGoogle Scholar
[12]Henderson, P. and Zalcstein, Y. (1977) A graph theoretic characterization of the PVchunk class of synchronizing primitives. SIAM J. Comp. 6 88–108.CrossRefGoogle Scholar
[13]Orlin, J. (1977) Contentment in Graph Theory: covering graphs with cliques. Indag. Math. 39 406–424.CrossRefGoogle Scholar
[14]Wallis, W. D. (1982) Asymptotic values of clique partition numbers. Combinatorica 2 (1) 99–101.CrossRefGoogle Scholar