Recognition of split-graphic sequences
From MaRDI portal
Publication:2254547
DOI10.1515/ausi-2015-0007zbMath1306.05097OpenAlexW419035954MaRDI QIDQ2254547
Antal Iványi, Bilal A. Chat, Shariefuddin Pirzada
Publication date: 5 February 2015
Published in: Acta Universitatis Sapientiae. Informatica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1515/ausi-2015-0007
linear time algorithmgraphic sequence\((a,b,n)\)-graphbsplit graphjsplit graphpotentially split sequencepsplit graph
Related Items (1)
Uses Software
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
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Hereditary unigraphs and Erdős-Gallai equalities
- A Rao-type characterization for a sequence to have a realization containing a split graph
- Certifying algorithms
- An exact bit-parallel algorithm for the maximum clique problem
- Conditions for sequences to be r-graphic
- Split digraphs
- The worst-case time complexity for generating all maximal cliques and computational experiments
- Covering a set by subsets
- Recognizing tough graphs is NP-hard
- A short constructive proof of the Erdős-Gallai characterization of graphic lists
- Minimal split completions
- A simple criterion on degree sequences of graphs
- A generalization of a conjecture due to Erdös, Jacobson and Lehel
- Conditions for \(r\)-graphic sequences to be potentially \(K^{(r)}_{m+1}\)-graphic
- Linear-time certifying algorithms for near-graphical sequences
- Necessary conditions for Hamiltonian split graphs
- Split graphs of Dilworth number 2
- The Erdős-Jacobson-Lehel conjecture on potentially \(P_k\)-graphic sequence is true
- The splittance of a graph
- Yet another method of enumerating unmarked combinatorial objects
- A note on Hamiltonian split graphs
- On probe interval graphs
- Split and balanced colorings of complete graphs
- The maximum clique problem
- Linear recognition of pseudo-split graphs
- Constant-time parallel recognition of split graphs
- The Erdős-Gallai criterion and symmetric functions
- Generalized split graphs and Ramsey numbers
- Graphs with no induced \(C_ 4\) and \(2K_ 2\)
- Toughness, hamiltonicity and split graphs
- Partitions of graphs into one or two independent sets and cliques
- An extension of A.R. Rao's characterization of potentially \(K_{m+1}\)-graphic sequences
- An extremal problem on the potentially \(P_k\)-graphic sequences
- A Rao-type characterization for a sequence to have a realization containing an arbitrary subgraph \(H\)
- Tough graphs and Hamiltonian circuits.
- Algorithms for constructing graphs and digraphs with given valences and factors
- Bisplit graphs
- Two sufficient conditions for a graphic sequence to have a realization with prescribed clique size
- Handbook of Graph Theory
- Colored Modular and Split Decompositions of Graphs with Applications to Trigraphs
- Potentially graphic sequences of split graphs
- Enumeration of graphs by degree sequence
- A remark on the existence of finite graphs
- Certifying Algorithms for Recognizing Interval Graphs and Permutation Graphs
- Reconstruction of complete interval tournaments. II
- On-line and first fit colorings of graphs
- On Realizability of a Set of Integers as Degrees of the Vertices of a Linear Graph. I
- Split Graphs Having Dilworth Number Two
- The Dilworth Number of a Graph
- Graph Classes: A Survey
- List Partitions
- A Havel-Hakimi type procedure and a sufficient condition for a sequence to be potentially S r,s -graphic
- Fully dynamic algorithms for chordal graphs and split graphs
- Some Properties of Graphs with Multiple Edges
This page was built for publication: Recognition of split-graphic sequences