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

DOI10.1016/J.DAM.2015.07.023MaRDI QIDQ344829zbMATH OpenOpenAlexWikidataFDO

Authors Endre Boros, Martin Milanič, Vladimir Gurvich

Publication date 24 November 2016

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

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

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)

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.

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

Cites work

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

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
• Equistarable graphs and counterexamples to three conjectures on equistable graphs
• Decomposing 1-Sperner hypergraphs
• 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)