k-Degenerate Graphs

DOI10.4153/CJM-1970-125-1zbMath0202.23502WikidataQ56235006 ScholiaQ56235006MaRDI QIDQ5599569

Don R. Lick, Arthur T. White

Publication date: 1970

Published in: Canadian Journal of Mathematics (Search for Journal in Brave)

Related Items

Close-knit neighborhoods: stability of cooperation in networks ⋮ Finding small complete subgraphs efficiently ⋮ Proximity Search for Maximal Subgraph Enumeration ⋮ A feedback vertex set of 2-degenerate graphs ⋮ Vertex partitions and maximum degenerate subgraphs ⋮ The space complexity of sum labelling ⋮ Point partition numbers: decomposable and indecomposable critical graphs ⋮ Weighted 2-sections and hypergraph reconstruction ⋮ Large survivable nets and the generalized prisms ⋮ Dense trees: a new look at degenerate graphs ⋮ Unnamed Item ⋮ Efficiently enumerating all maximal cliques with bit-parallelism ⋮ A polynomial-time approximation to a minimum dominating set in a graph ⋮ Treewidth for graphs with small chordality ⋮ Wiener indices of maximal \(k\)-degenerate graphs ⋮ Angle Covers: Algorithms and Complexity ⋮ Some bounds on the generalised total chromatic number of degenerate graphs ⋮ A bound on the values of independence polynomials at \(-1/k\) for \(k\)-degenerate graphs ⋮ Drawing Planar Graphs with Few Geometric Primitives ⋮ Hardness of Approximate Compaction for Nonplanar Orthogonal Graph Drawings ⋮ Extremal decompositions for Nordhaus-Gaddum theorems ⋮ An Updated Experimental Evaluation of Graph Bipartization Methods ⋮ Partitions of hypergraphs under variable degeneracy constraints ⋮ ON THE DIMENSIONS OF THE REALIZATION SPACES OF POLYTOPES ⋮ Central Limit Theorem for Linear Eigenvalue Statistics of <scp>Non‐Hermitian</scp> Random Matrices ⋮ Sequences realizable by maximal k‐degenerate graphs ⋮ Generalized DP-colorings of graphs ⋮ Extremal problems for connected set enumeration ⋮ On edge product cordial graphs ⋮ Erdős-Hajnal well-orderings and n-degenerate graphs ⋮ Cusp universality for random matrices. I: Local law and the complex Hermitian case ⋮ The high order spectrum of a graph and its applications in graph colouring and clique counting ⋮ Locally identifying colourings for graphs with given maximum degree ⋮ Sparsity measure of a network graph: Gini index ⋮ Irregularities of maximal \(k\)-degenerate graphs ⋮ On graphs critical with respect to vertex partition numbers ⋮ Bounds on half graph orders in powers of sparse graphs ⋮ Edge-intersection graphs of grid paths: the bend-number ⋮ Unnamed Item ⋮ Sharp bounds of the Zagreb indices of \(k\)-trees ⋮ Constraint and Satisfiability Reasoning for Graph Coloring ⋮ Improved bounds for the chromatic index of graphs and multigraphs ⋮ An inequality involving the vertex arboricity and edge arboricity of a graph ⋮ Critically partitionable graphs. II ⋮ Beyond Outerplanarity ⋮ Note on coloring of double disk graphs ⋮ A search problem on graphs which generalizes some group testing problems with two defectives ⋮ Solving maximum clique in sparse graphs: an \({O(nm+n2^{d/4})}\) algorithm for \(d\)-degenerate graphs ⋮ Why Is Maximum Clique Often Easy in Practice? ⋮ Maximum 4-degenerate subgraph of a planar graph ⋮ A new decomposition technique for maximal clique enumeration for sparse graphs ⋮ Efficient enumeration of maximal induced bicliques ⋮ Efficient enumeration of dominating sets for sparse graphs ⋮ Consecutive colouring of oriented graphs ⋮ Reconfiguration on sparse graphs ⋮ Eigenstate thermalization hypothesis for Wigner matrices ⋮ In search of the densest subgraph ⋮ Independence polynomials of \(k\)-tree related graphs ⋮ Partitioning a graph into degenerate subgraphs ⋮ The space complexity of sum labelling ⋮ Note to the paper of Grünbaum on acyclic colorings ⋮ On mixed Ramsey numbers ⋮ Joins of n-degenerate graphs and uniquely (m,n)-partitionable graphs ⋮ The parameterized complexity of editing graphs for bounded degeneracy ⋮ An extension of Brooks' theorem to n-degenerate graphs ⋮ Unnamed Item ⋮ Total rainbow connection numbers of some special graphs ⋮ Some results in topological graph theory ⋮ Degree sequences of monocore graphs ⋮ Colourings of (k-r,k)-trees ⋮ A constant amortized time enumeration algorithm for independent sets in graphs with bounded clique number ⋮ On a cycle partition problem ⋮ k-Blocks and Ultrablocks in Graphs ⋮ On the support of extremal martingale measures with given marginals: the countable case ⋮ The k-conversion number of regular graphs ⋮ Vertex partition of hypergraphs and maximum degenerate subhypergraphs ⋮ On chordal phylogeny graphs ⋮ Edge Bounds and Degeneracy of Triangle-Free Penny Graphs and Squaregraphs ⋮ Unnamed Item ⋮ Incremental optimization of independent sets under the reconfiguration framework ⋮ Computing the depth distribution of a set of boxes ⋮ -constructibility of planar graphs ⋮ Chromatic partitions of a graph ⋮ -constructibility of planar graphs ⋮ Coloring geometric range spaces ⋮ The largest eigenvalue of a graph: A survey ⋮ The subchromatic number of a graph ⋮ A note on graphs with prescribed clique and point-partition numbers ⋮ On zero-sum spanning trees and zero-sum connectivity ⋮ Parameterized leaf power recognition via embedding into graph products ⋮ The clique-perfectness and clique-coloring of outer-planar graphs ⋮ Worst-case analysis of clique MIPs ⋮ The game coloring number of planar graphs ⋮ Point Partition Numbers and Girth ⋮ Graph factorization and theorems of the Nordhaus-Gaddum class ⋮ Locally defined independence systems on graphs ⋮ Upper bound for linear arboricity ⋮ Point partition numbers: perfect graphs ⋮ On primes and practical numbers ⋮ Ergodicity of the Wang–Swendsen–Kotecký algorithm on several classes of lattices on the torus ⋮ Lower bounds for the independence and \(k\)-independence number of graphs using the concept of degenerate degrees

This page was built for publication: k-Degenerate Graphs