The splittance of a graph
From MaRDI portal
Publication:1167741
DOI10.1007/BF02579333zbMath0492.05043OpenAlexW2064721098MaRDI QIDQ1167741
Peter L. Hammer, Bruno Simeone
Publication date: 1981
Published in: Combinatorica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/bf02579333
Related Items
Forcibly bipartite and acyclic (uni-)graphic sequences, Graph realizations: maximum degree in vertex neighborhoods, Transitivity on subclasses of chordal graphs, Nonsplit Graphs with Split Maximal Induced Subgraphs, A survey of parameterized algorithms and the complexity of edge modification, Split graphs and block representations, Comparing eigenvector and degree dispersion with the principal ratio of a graph, Complexity classification of some edge modification problems, Split graphs, A polynomial time algorithm for geodetic hull number for complementary prisms, Linear recognition of pseudo-split graphs, About recognizing (\(\alpha\) ,\(\beta\) ) classes of polar graphs, Computing role assignments of split graphs, On degree sequences and eccentricities in pseudoline arrangement graphs, Win-win kernelization for degree sequence completion problems, The independence coloring game on graphs, The bipartite-splittance of a bipartite graph, Split graphs and Nordhaus-Gaddum graphs, Editing Graphs Into Few Cliques: Complexity, Approximation, and Kernelization Schemes, On the intersection graphs of orthogonal line segments in the plane: characterizations of some subclasses of chordal graphs, Recognizing well covered graphs of families with special \(P _{4}\)-components, \(P_{4}\)-laden graphs: A new class of brittle graphs, Coloring perfect degenerate graphs, Dominating sets whose closed stars form spanning trees, On the use of Boolean methods for the computation of the stability number, Minimum edge ranking spanning trees of split graphs, Rainbow colouring of split graphs, Algorithms for deletion problems on split graphs, Partitions of graphs into one or two independent sets and cliques, An algorithm for coloring some perfect graphs, Parameterized algorithms for recognizing monopolar and 2-subcolorable graphs, Fast recognition of doubled graphs, Subgraph complementation, Hereditary unigraphs and Erdős-Gallai equalities, On vertex-weighted realizations of acyclic and general graphs, Weighted Efficient Domination for $P_5$-Free and $P_6$-Free Graphs, On fractional realizations of graph degree sequences, Editing to Eulerian graphs, Cliques in Regular Graphs and the Core-Periphery Problem in Social Networks, The firefighter problem on graph classes, Unnamed Item, Classes of perfect graphs, A Characterization of the degree sequences of 2-trees, Split orders, A fully dynamic algorithm for modular decomposition and recognition of cographs., Co-TT graphs and a characterization of split co-TT graphs, Graphs and degree sequences. I, Minimum Fill-In and Treewidth of Split+ ke and Split+ kv Graphs, Representations of graphs and networks (coding, layouts and embeddings), Split dimension of graphs, LINEAR TIME RECOGNITION AND OPTIMIZATIONS FOR WEAK-BISPLIT GRAPHS, BI-COGRAPHS AND BIPARTITE P6-FREE GRAPHS, Constraints on Brouwer's Laplacian spectrum conjecture, Difference graphs, Coloring perfect graphs with no balanced skew-partitions, Finding disjoint paths in split graphs, Non-minimal degree-sequence-forcing triples, New Classes of Degree Sequences with Fast Mixing Swap Markov Chain Sampling, Simple groups whose Gruenberg-Kegel graph or solvable graph is split, Finding balance: split graphs and related classes, Contributions to the theory of graphic sequences, The Grone-Merris Conjecture, Adjacency relationships forced by a degree sequence, Recognition of split-graphic sequences, Split graphs: combinatorial species and asymptotics, On the Grundy number of graphs with few \(P_4\)'s, Minimal split completions, Minimum fill-in and treewidth of split \(+ ke\) and split \(+kv\) graphs, On the interval completion of chordal graphs, NP-completeness results for edge modification problems, Dichotomy for tree-structured trigraph list homomorphism problems, Groups for which the noncommuting graph is a split graph, Unnamed Item, The polytope of degree sequences, Computing the boxicity of a graph by covering its complement by cointerval graphs, Antimagic labeling and canonical decomposition of graphs, On split-coloring problems, Maximum rooted connected expansion, Cluster deletion on interval graphs and split related graphs, Subexponential parameterized algorithms and kernelization on almost chordal graphs, Half-graphs, other non-stable degree sequences, and the switch Markov chain, Dominating sequences in graphs, Automated generation of conjectures on forbidden subgraph characterization, Subset feedback vertex set in chordal and split graphs, On the threshold of intractability, Parameterized complexity of vertex colouring, Dynamically maintaining split graphs, On forcibly hereditary P-graphical sequences, Reconstructing Cactus Graphs from Shortest Path Information, Split digraphs, Unnamed Item, The complexity of some problems related to GRAPH 3-COLORABILITY, Incompressibility of \(H\)-free edge modification problems: towards a dichotomy, Hardness of edge-modification problems, The principal Erdős-Gallai differences of a degree sequence, Degree Sequence of Tight Distance Graphs, The graph of atomic divisors and recognition of finite simple groups, Counting and enumerating independent sets with applications to combinatorial optimization problems, ON GRAPHS WITH LIMITED NUMBER OF P4-PARTNERS, BIPARTITE GRAPHS TOTALLY DECOMPOSABLE BY CANONICAL DECOMPOSITION, The realization graph of a degree sequence with majorization gap 1 is Hamiltonian, The network flows approach for matrices with given row and column sums, Graph Classes and Forbidden Patterns on Three Vertices, (Sub)linear kernels for edge modification problems toward structured graph classes, Degree sequences of matrogenic graphs, Minimal forbidden sets for degree sequence characterizations, On vertex ranking of a starlike graph, Faster parameterized algorithms for deletion to split graphs, Relaxed and approximate graph realizations
Cites Work
