On split and almost CIS-graphs

Endre Boros, Vladimir Gurvich, Igor Zverovich

Research output: Contribution to journalArticle

10 Scopus citations

Abstract

A CIS-graph is defined as a graph whose every maximal clique and stable set intersect. These graphs have many interesting properties, yet, it seems difficult to obtain an efficient characterization and/or polynomial-time recognition algorithm for CIS-graphs. An almost CIS-graph is defined as a graph that has a unique pair (Ce S) of disjoint maximal clique C and stable sets S. We conjecture that almost CIS-graphs are exactly split graphs that have a unique split par- tition and prove this conjecture for a large hereditary class of graphs that contains, for example, chordal graphs and P 5-free graphs, as well as their complements, etc. We also prove the conjecture in case \C\ = \S\ = 2 and show that the vertex-set R = V \ (C U S) cannot induce a threshold graph, although we do not prove that R = 0, as the conjecture suggests.

Original languageEnglish (US)
Pages (from-to)163-180
Number of pages18
JournalAustralasian Journal of Combinatorics
Volume43
StatePublished - Feb 1 2009

All Science Journal Classification (ASJC) codes

  • Discrete Mathematics and Combinatorics

Fingerprint Dive into the research topics of 'On split and almost CIS-graphs'. Together they form a unique fingerprint.

  • Cite this

    Boros, E., Gurvich, V., & Zverovich, I. (2009). On split and almost CIS-graphs. Australasian Journal of Combinatorics, 43, 163-180.