Orientations of graphs with prescribed weighted out-degrees

DOI10.1007/S00373-013-1382-0zbMATH Open1306.05089OpenAlexW1984574113MaRDI QIDQ489364FDOQ489364

Authors: Michael Stiebitz, Zsolt Tuza, Margit Voigt 

Publication date: 20 January 2015

Published in: Graphs and Combinatorics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00373-013-1382-0

Recommendations

• Approximation algorithms for the graph orientation minimizing the maximum weighted outdegree
• On the complexity of finding well-balanced orientations with upper bounds on the out-degrees
• Approximation Algorithms for the Graph Orientation Minimizing the Maximum Weighted Outdegree
• The hardness of the functional orientation 2-color problem
• An oriented version of the 1-2-3 conjecture

zbMATH Keywords

chromatic numberorientationsBrooks' theoremkernelsvertex weighted graphs

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Signed and weighted graphs (05C22)

Cites Work

• Incidence matrices and interval graphs
• On the degrees of the vertices of a directed graph
• Solutions of irreflexive relations
• Title not available (Why is that?)
• Title not available (Why is that?)
• List colourings of graphs
• Graph colorings with local constraints -- a survey
• On Representatives of Subsets
• On the complexity of the disjoint paths problem
• The list chromatic index of a bipartite multigraph
• Title not available (Why is that?)
• Nombre chromatique et plus longs chemins d'un graphe
• Colorings and orientations of graphs
• On chromatic number of graphs and set-systems
• Title not available (Why is that?)
• Zur algebraischen Begründung der Graphentheorie. I
• Brooks' theorem via the Alon-Tarsi theorem
• Graph coloring in linear time
• Title not available (Why is that?)
• Title not available (Why is that?)
• A solution to a colouring problem of P. Erdős
• Edge-choosability of multicircuits
• List \(T\)-colorings of graphs
• Choosability of powers of circuits
• Title not available (Why is that?)
• Title not available (Why is that?)

Cited In (6)

• Graph classes and the complexity of the graph orientation minimizing the maximum weighted outdegree
• The robust chromatic number of graphs
• On the in-out-proper orientations of graphs
• The edge-orientation problem and some of its variants on weighted graphs
• On finding orientations with the fewest number of vertices with small out-degree
• The hardness of the functional orientation 2-color problem

This page was built for publication: Orientations of graphs with prescribed weighted out-degrees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q489364)