Characterizations of derived graphs

DOI10.1016/S0021-9800(70)80019-9zbMath0202.55702OpenAlexW2065761231WikidataQ56388823 ScholiaQ56388823MaRDI QIDQ5601346

Lowell W. Beineke

Publication date: 1970

Published in: Journal of Combinatorial Theory (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0021-9800(70)80019-9

Related Items (only showing first 100 items - show all)

A \(\vec{P_3}\)-decomposition of tournaments and bipartite digraphs ⋮ The staggered quantum walk model ⋮ Characterizations of line graphs in signed and gain graphs ⋮ On leap indices of CNC_k[n by using line operator on its subdivision] ⋮ Unnamed Item ⋮ Vertex coloring \((4K_1\), hole-twin, 5-wheel)-free graphs ⋮ Graphs with induced-saturation number zero ⋮ Clique-coloring of \(K_{3,3}\)-minor free graphs ⋮ Heavy subgraphs, stability and Hamiltonicity ⋮ On coloring a class of claw-free graphs. ⋮ A simple upper bound for the hamiltonian index of a graph ⋮ Induced cycles in triangle graphs ⋮ Application of cut polyhedra. I ⋮ Mock threshold graphs ⋮ Index of parameters of iterated line graphs ⋮ Number of colors needed to break symmetries of a graph by an arbitrary edge coloring ⋮ Hamilton-connectedness and Hamilton-laceability of planar geometric graphs with applications ⋮ Claw-free graphs---a survey ⋮ On the structure of graphs without claw, \(4K_1\) and co-R ⋮ Tight Frame Graphs Arising as Line Graphs ⋮ Graph isomorphism for graph classes characterized by two forbidden induced subgraphs ⋮ Polynomial kernelization for removing induced claws and diamonds ⋮ Binary contraction of graphs ⋮ On line graphs of subcubic triangle-free graphs ⋮ Forbidden graphs for degree and neighbourhood conditions ⋮ Claw-free strictly Deza graphs ⋮ From matchings to independent sets ⋮ Even cycles and even 2-factors in the line graph of a simple graph ⋮ Reconstructing a graph from its arc incidence graph ⋮ On polynomial kernelization of \(\mathcal H\)-\textsc{free edge deletion} ⋮ Triangle packings and transversals of some \(K_{4}\)-free graphs ⋮ Generalized line graphs: Cartesian products and complexity of recognition ⋮ A coloring algorithm for \(4 K_1\)-free line graphs ⋮ A characterization of line graphs that are squares of graphs ⋮ The signature of two generalizations of line graphs ⋮ Enumeration of substitutional isomers with restrictive mutual positions of ligands: I. Overall counts ⋮ The Capacitated and Economic Districting Problem ⋮ Unnamed Item ⋮ Packing cycles in graphs ⋮ The maximum cardinality cut problem in co-bipartite chain graphs ⋮ List monopolar partitions of claw-free graphs ⋮ Characterization of classical graph classes by weighted clique graphs ⋮ On contact graphs of paths on a grid ⋮ How many conjectures can you stand? A survey ⋮ Equivalence of four descriptions of generalized line graphs ⋮ Binary representations of regular graphs ⋮ Line graphs of bounded clique-width ⋮ An incremental polynomial time algorithm to enumerate all minimal edge dominating sets ⋮ Unnamed Item ⋮ Minimal line graphs ⋮ NP-hard graph problems and boundary classes of graphs ⋮ On the complexity of generalized chromatic polynomials ⋮ A polynomial-time algorithm for the maximum cardinality cut problem in proper interval graphs ⋮ Free fermions behind the disguise ⋮ Degree conditions restricted to induced paths for Hamiltonicity of claw-heavy graphs ⋮ On the strong chromatic index and maximum induced matching of tree-cographs, permutation graphs and chordal bipartite graphs ⋮ On edge-sets of bicliques in graphs ⋮ Structure of 4-connected claw-free graphs not containing a subdivision of \(K_{5}\) ⋮ On clique immersions in line graphs ⋮ Closure and forbidden pairs for 2-factors ⋮ Graphs with least eigenvalue \(-2\): a new proof of the 31 forbidden subgraphs theorem ⋮ Fixed-Point Definability and Polynomial Time on Chordal Graphs and Line Graphs ⋮ Unnamed Item ⋮ A bibliography of graph equations ⋮ Finding the root graph through minimum edge deletion ⋮ On a relation between \(k\)-path partition and \(k\)-path vertex cover ⋮ A characterization of 2-tree probe interval graphs ⋮ Contractible subgraphs, Thomassen's conjecture and the dominating cycle conjecture for snarks ⋮ Perfect Graphs with No Balanced Skew-Partition are 2-Clique-Colorable ⋮ Automated generation of conjectures on forbidden subgraph characterization ⋮ Quartic Graphs with Every Edge in a Triangle ⋮ On graphs whose second largest eigenvalue is at most 1 ⋮ Line graphs of multigraphs and Hamilton-connectedness of claw-free graphs ⋮ Unnamed Item ⋮ The intersection of two vertex coloring problems ⋮ A characterization of signed graphs represented by root system \(D_ \infty\) ⋮ On spectral characterization and embeddings of graphs ⋮ Even-hole-free graphs that do not contain diamonds: A structure theorem and its consequences ⋮ Polynomial Kernelization for Removing Induced Claws and Diamonds ⋮ Unnamed Item ⋮ Connected greedy coloring of \(H\)-free graphs ⋮ Characterization of n-path graphs and of graphs having \(n\)-th root ⋮ Counting Weighted Independent Sets beyond the Permanent ⋮ Pancyclicity of claw-free Hamiltonian graphs ⋮ Resolving Stanley's \(e\)-positivity of claw-contractible-free graphs ⋮ Unnamed Item ⋮ Sprague-Grundy function of matroids and related hypergraphs ⋮ Disjoint paired-dominating sets in cubic graphs ⋮ On coloring a class of claw-free and hole-twin-free graphs ⋮ The structure of graphs with forbidden induced $C_4$, $\overline{C}_4$, $C_5$, $S_3$, chair and co-chair ⋮ The clique-transversal number of a \(\{K_{1, 3}, K_4 \}\)-free 4-regular graph ⋮ The feasibility problem for line graphs ⋮ Graphoidal graphs and graphoidal digraphs: a generalization of line graphs ⋮ Graphs with least eigenvalue \(-2\); a historical survey and recent developments in maximal exceptional graphs ⋮ On \(\bullet\)-line signed graphs \(L_\bullet(S)\) ⋮ Forbidden subgraphs for longest cycles to contain vertices with large degrees ⋮ The dynamics of the line and path graph operators ⋮ Contractible Subgraphs, Thomassen's Conjecture and the Dominating Cycle Conjecture for Snarks ⋮ A complete characterization of graphs with exactly two positive eigenvalues ⋮ Set graphs. III: Proof pearl: Claw-free graphs mirrored into transitive hereditarily finite sets

This page was built for publication: Characterizations of derived graphs