On equistable, split, CIS, and related classes of graphs

DOI10.1016/J.DAM.2015.07.023zbMATH Open1350.05117arXiv1505.05683OpenAlexW2119925787WikidataQ59560467 ScholiaQ59560467MaRDI QIDQ344829FDOQ344829

Authors: Endre Boros, Martin Milanič, Vladimir Gurvich 

Publication date: 24 November 2016

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Abstract: We consider several graphs classes defined in terms of conditions on cliques and stable sets, including CIS, split, equistable, and other related classes. We pursue a systematic study of the relations between them. As part of this study, we introduce two generalizations of CIS graphs, obtain a new characterization of split graphs, and a characterization of CIS line graphs.

Full work available at URL: https://arxiv.org/abs/1505.05683

Recommendations

• On split and almost CIS-graphs
• A characterization of almost CIS graphs
• Equistable simplicial, very well-covered, and line graphs
• A class of threshold and domishold graphs: Equistable and equidominating graphs
• Equistable graphs

zbMATH Keywords

split graphcliqueequistable graphgeneral partition graphtriangle conditionnormal graphstable setCIS graphedge simplicial graphupper bound graph

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph operations (line graphs, products, etc.) (05C76)

Cites Work

• Graph Classes: A Survey
• Some covering concepts in graphs
• Efficient algorithms for minimum weighted colouring of some classes of perfect graphs
• Equistable series-parallel graphs
• Equistable chordal graphs
• Generalizations of Grillet's theorem on maximal stable sets and maximal cliques in graphs
• Threshold graphs and related topics
• A \(max \{m, n \}\) algorithm for determining the graph H from its line graph G
• On the complexity of the independent set problem in triangle graphs
• Equistable graphs, general partition graphs, triangle graphs, and graph products
• A characterization and hereditary properties for partition graphs
• Recent examples in the theory of partition graphs
• Equistable simplicial, very well-covered, and line graphs
• Equistable distance-hereditary graphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Equistable graphs
• Faster scaling algorithms for general graph matching problems
• Title not available (Why is that?)
• Graph-Theoretic Concepts in Computer Science
• A class of threshold and domishold graphs: Equistable and equidominating graphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• Partitions of graphs into one or two independent sets and cliques
• Cycle transversals in perfect graphs and cographs
• Split Graphs Having Dilworth Number Two
• The complexity of some problems related to GRAPH 3-COLORABILITY
• Partitioning graphs into complete and empty graphs
• Vertex-transitive CIS graphs
• Constructions for normal graphs and some consequences
• Stochastic graphs and strongly perfect graphs - a survey
• On the odd cycles of normal graphs
• On stable cutsets in graphs
• On graphs whose maximal cliques and stable sets intersect
• Line-graphs of cubic graphs are normal
• Bipartite bihypergraphs: a survey and new results
• Partition the vertices of a graph into one independent set and one acyclic set
• Bisplit graphs
• The Normal Graph Conjecture for Classes of Sparse Graphs
• Graphs that Split Entropies
• Title not available (Why is that?)
• The normal graph conjecture is true for circulants
• Independent Domination in Triangle Graphs
• A characterization of almost CIS graphs
• On split and almost CIS-graphs
• Title not available (Why is that?)
• On CIS circulants
• Two-step encoding for finite sources
• Title not available (Why is that?)
• A Survey of the Algorithmic Properties of Simplicial, Upper Bound and Middle Graphs
• Cross‐intersecting couples of graphs
• On exact blockers and anti-blockers, \(\varDelta \)-conjecture, and related problems
• Entropy splitting for antiblocking corners and perfect graphs
• A note on the computational complexity of graph vertex partition
• Not complementary connected and not CIS \(d\)-graphs form weakly monotone families
• Decomposing complete edge-chromatic graphs and hypergraphs. Revisited

Cited In (12)

• Short proofs on the structure of general partition, equistable and triangle graphs
• Strong cliques and equistability of EPT graphs
• Detecting strong cliques
• Strong cliques in diamond-free graphs
• Strong cliques in vertex‐transitive graphs
• 1-Triangle graphs and perfect neighborhood sets
• A characterization of claw-free CIS graphs and new results on the order of CIS graphs
• Decomposing 1-Sperner hypergraphs
• Equistarable Graphs and Counterexamples to Three Conjectures on Equistable Graphs
• Graphs vertex-partitionable into strong cliques
• On split and almost CIS-graphs
• A characterization of almost CIS graphs

This page was built for publication: On equistable, split, CIS, and related classes of graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q344829)