Orientations of graphs with prescribed weighted out-degrees

DOI10.1007/S00373-013-1382-0MaRDI QIDQ489364zbMATHOpenAlexFDO

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

zbMATH Keywords

chromatic numberorientationsBrooks' theoremkernelsvertex weighted graphs

Mathematics Subject Classification ID

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

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

Cites work

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

Cited in

(6)

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

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)