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, On the Neighbor Sum Distinguishing Index of Planar Graphs, 3-Regular subgraphs and (3,1)-colorings of 4-regular pseudographs, Total Weight Choosability of Trees, Neighbour sum distinguishing total colourings via the combinatorial nullstellensatz, A note on adjacent vertex distinguishing colorings of graphs, Group sum chromatic number of graphs, Total edge irregularity strength of generalized prism, On decomposing graphs of large minimum degree into locally irregular subgraphs, The 3-flow conjecture, factors modulo \(k\), and the 1-2-3-conjecture, Algorithmic complexity of proper labeling problems, Distant irregularity strength of graphs, Colour-blind can distinguish colour pallets, Computation of lucky number of planar graphs is NP-hard, On the approximability of some degree-constrained subgraph problems, The \(1,2,3\)-conjecture and \(1,2\)-conjecture for sparse graphs, A note on vertex colorings of plane graphs, Total weight choosability of Mycielski graphs, On weight choosabilities of graphs with bounded maximum average degree, 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, Colourings of graphs by labellings, Distant sum distinguishing index of graphs, On decomposing regular graphs into locally irregular subgraphs, Vertex-coloring 3-edge-weighting of some graphs, The edge-labeling and vertex-colors of \(K_n\), Distant irregularity strength of graphs with bounded minimum degree, On approximating the \(d\)-girth of a graph, The complexity of the proper orientation number, A note on face coloring entire weightings of plane graphs, Weak and strong versions of the 1-2-3 conjecture for uniform hypergraphs, A relaxed case on 1-2-3 conjecture, Neighbor sum distinguishing index of \(K_4\)-minor free graphs, Neighbor sum distinguishing edge colorings of graphs with bounded maximum average degree, On Approximating the d-Girth of a Graph, Neighbor Distinguishing Edge Colorings Via the Combinatorial Nullstellensatz Revisited, 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