Degree constrained subgraphs

DOI10.1016/j.dam.2007.05.059zbMath1147.05055MaRDI QIDQ2482112

Louigi Addario-Berry, Bruce A. Reed, Ketan Dalal

Publication date: 16 April 2008

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2007.05.059

zbMATH Keywords

vertex colouring; edge weighting; degree constrained subgraphs

Mathematics Subject Classification ID

05C75: Structural characterization of families of graphs

05C15: Coloring of graphs and hypergraphs

Related Items

NEIGHBOR SUM DISTINGUISHING COLORING OF SOME GRAPHS, Algorithmic complexity of proper labeling problems, Distant irregularity strength of graphs, Computation of lucky number of planar graphs is NP-hard, On the approximability of some degree-constrained subgraph problems, Vertex-coloring 2-edge-weighting of graphs, Coloring chip configurations on graphs and digraphs, Vertex-coloring edge-weightings: towards the 1-2-3-conjecture, Lucky labelings of graphs, On vertex-coloring 13-edge-weighting, Edge irregular total labellings for graphs of linear size, The edge-labeling and vertex-colors of \(K_n\), Neighbor sum distinguishing edge colorings of graphs with bounded maximum average degree, On Approximating the d-Girth of a Graph, Degree-Constrained Subgraph Problems: Hardness and Approximation Results, Weight choosability of graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A simple existence criterion for \((g<f)\)-factors
• Matching theory
• General antifactors of graphs
• Edge weights and vertex colours
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Vertex-colouring edge-weightings
• Vertex colouring edge partitions
• The Harmonious Chromatic Number of Bounded Degree Graphs
• The factorization of graphs. II