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

DOI10.1016/j.dam.2015.07.023zbMath1350.05117arXiv1505.05683OpenAlexW2119925787WikidataQ59560467 ScholiaQ59560467MaRDI QIDQ344829

Endre Boros, Martin Milanič, Vladimir A. 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 graphstable setcliquetriangle conditionequistable graphgeneral partition graphnormal graphCIS graphedge simplicial graphupper bound graph

Mathematics Subject Classification ID

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

Related Items (10)

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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On CIS circulants
• Vertex-transitive CIS graphs
• On exact blockers and anti-blockers, \(\varDelta \)-conjecture, and related problems
• A class of threshold and domishold graphs: Equistable and equidominating graphs
• 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
• Constructions for normal graphs and some consequences
• Partitioning graphs into complete and empty graphs
• Stochastic graphs and strongly perfect graphs - a survey
• The complexity of some problems related to GRAPH 3-COLORABILITY
• On the odd cycles of normal graphs
• Efficient algorithms for minimum weighted colouring of some classes of perfect graphs
• Equistable series-parallel graphs
• Equistable chordal graphs
• On stable cutsets in graphs
• Generalizations of Grillet's theorem on maximal stable sets and maximal cliques in graphs
• Threshold graphs and related topics
• Partitions of graphs into one or two independent sets and cliques
• Cycle transversals in perfect graphs and cographs
• 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
• On graphs whose maximal cliques and stable sets intersect
• A characterization and hereditary properties for partition graphs
• Recent examples in the theory of partition graphs
• Line-graphs of cubic graphs are normal
• Equistable simplicial, very well-covered, and line graphs
• Equistable distance-hereditary graphs
• 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
• Independent Domination in Triangle Graphs
• A Characterization of Almost CIS Graphs
• Split Graphs Having Dilworth Number Two
• Graph Classes: A Survey
• Equistable graphs
• Faster scaling algorithms for general graph matching problems
• Two-step encoding for finite sources
• A Survey of the Algorithmic Properties of Simplicial, Upper Bound and Middle Graphs
• Cross‐intersecting couples of graphs
• Some covering concepts in graphs
• Graph-Theoretic Concepts in Computer Science

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