More characterizations of triangulated graphs

[en] New characterizations of triangulated and cotriangulated graphs are presented. Cotriangulated graphs form a natural subclass of the class of strongly perfect graphs, and they are also characterized in terms of the shellability of some associated collection of sets. Finally, the notion of stability function of a graph is introduced, and it is proved that a graph is triangulated if and only if the polynomial representing its stability function has all its coefficients equal to 0, +1 or −1.

Disciplines :

Mathematics

Author, co-author :

Benzaken, Claude

Crama, Yves ; Université de Liège - ULiège > HEC Liège : UER > Recherche opérationnelle et gestion de la production

Duchet, Pierre

Hammer, Peter L.

Maffray, Frédéric

Language :

English

Title :

More characterizations of triangulated graphs

Publication date :

1990

Journal title :

Journal of Graph Theory

ISSN :

0364-9024

eISSN :

1097-0118

Publisher :

Wiley

Volume :

Issue :

Pages :

413-422

Peer reviewed :

Peer Reviewed verified by ORBi

Available on ORBi :

since 23 December 2017

Statistics

Number of views

69 (2 by ULiège)

Number of downloads

1 (1 by ULiège)

More statistics

Scopus citations^®

Scopus citations^®
without self-citations

OpenCitations

OpenAlex citations

See more details

publications

supporting

mentioning

contrasting

Smart Citations

Citing PublicationsSupportingMentioningContrasting

View Citations

See how this article has been cited at scite.ai

scite shows how a scientific paper has been cited by providing the context of the citation, a classification describing whether it supports, mentions, or contrasts the cited claim, and a label indicating in which section the citation was made.

Bibliography

Ball M.O., Nemhauser G.L. (1979) Matroids and a reliability analysis problem. Math. Oper. Res. 4:132-143.
Ball M.O., Provan J.S. (1982) Bounds on the reliability polynomial for shellable independence systems. SIAM Journal on Algebraic Discrete Methods 3:166-181.
Ball M.O., Provan J.S., Disjoint products and efficient computation of reliability, Technical report UNC/ORSA/TR‐86/13, University of North Carolina, Chapel Hill, NC; 1986.
Berge C. (1960) Les problèmes de coloration en theorie des graphes. Publ. Inst. Stat. Univ. Paris 9:123-160.
Berge C., Duchet P., Strongly perfect graphs, Topics on Perfect Graphs. North‐Holland, Amsterdam; 1984, 57-61.
Brugesser H., Mani P. (1971) Shellable decompositions of cells and spheres. Math. Scand. 29:199-205.
Danaraj G., Klee V. (1974) Shellings of spheres and polytopes. Duke Mathematical Journal 41:443-451.
Duchet P., Classical perfect graphs. Topics on Perfect Graphs. North‐Holland, Amsterdam; 1984, 67-96.
Golumbic M.C. Algorithmic Graph Theory and Perfect Graphs, Academic Press, New York; 1980.
Hajnal A., Surányi J. (1958) Über die Auflösung von Graphen in vollständige Teilgraphen. Ann. Univ. Sc. Budapestinensis 1:113-121.
Hammer P.L., Rudeanu S. Boolean Methods in Operations Research and Related Areas, Springer, Berlin, Heidelberg, New York; 1968.

Name	Provider / Domaine	Expiration	Description
JSESSIONID	Oracle Corporation www.uliege.be	Session	General purpose platform session cookie, used by sites written in JSP. Usually used to maintain an anonymous user session by the server.
CookieScriptConsent	CookieScript .uliege.be	1 year	This cookie is used by Cookie-Script.com service to remember visitor cookie consent preferences. It is necessary for Cookie-Script.com cookie banner to work properly.

Name	Provider / Domaine	Expiration	Description
_pk_id	InnoCraft Ltd .uliege.be	1 year	Used to store a few details about the user such as the unique visitor ID
_pk_ses	InnoCraft Ltd .uliege.be	30 minutes	Short lived cookies used to temporarily store data for the visit
_pk_ref	InnoCraft Ltd .uliege.be	6 months	Used to store the attribution information, the referrer initially used to visit the website