A min-max relation for the partial q-colourings of a graph. II: Box perfection

DOI10.1016/0012-365X(89)90194-5MaRDI QIDQ752726zbMATH OpenOpenAlexFDO

Authors Kathie Cameron

Publication date 1989

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0012-365x(89)90194-5

zbMATH Keywords

totally unimodular matrixcomparability graphslinear programbox perfectionmin-max equality

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Programming involving graphs or networks (90C35) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Coloring of graphs and hypergraphs (05C15)

Recommendations

• On box-perfect graphs
• Minimax relations for the partial q-colorings of a graph
• scientific article; zbMATH DE number 861396
• scientific article; zbMATH DE number 3851153
• scientific article; zbMATH DE number 4059461

Cites work

• scientific article; zbMATH DE number 3885657 (Why is no real title available?)
• scientific article; zbMATH DE number 3121293 (Why is no real title available?)
• scientific article; zbMATH DE number 3851153 (Why is no real title available?)
• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• scientific article; zbMATH DE number 4089320 (Why is no real title available?)
• scientific article; zbMATH DE number 3177183 (Why is no real title available?)
• scientific article; zbMATH DE number 3758364 (Why is no real title available?)
• scientific article; zbMATH DE number 3472052 (Why is no real title available?)
• scientific article; zbMATH DE number 3557519 (Why is no real title available?)
• scientific article; zbMATH DE number 3580570 (Why is no real title available?)
• A characterization of perfect graphs
• A decomposition theorem for partially ordered sets
• Anti-blocking polyhedra
• Balanced matrices
• Blocking and anti-blocking pairs of polyhedra
• Characterizations of strongly chordal graphs
• Coflow polyhedra
• Minimax relations for the partial q-colorings of a graph
• Normal hypergraphs and the perfect graph conjecture
• On certain polytopes associated with graphs
• On switching paths polyhedra
• On the facial structure of set packing polyhedra
• Some partitions associated with a partially ordered set
• The structure of Sperner k-families

Cited in

(13)

• A discrete convex min-max formula for box-TDI polyhedra
• Clique partitioning with value-monotone submodular cost
• scientific article; zbMATH DE number 4059461 (Why is no real title available?)
• Clique partitioning of interval graphs with submodular costs on the cliques
• Graph covers using \(t\)-colourable vertex sets.
• scientific article; zbMATH DE number 554064 (Why is no real title available?)
• On box-perfect graphs
• Box-total dual integrality, box-integrality, and equimodular matrices
• A weak box-perfect graph theorem
• Minimax relations for the partial q-colorings of a graph
• The maximum vertex coverage problem on bipartite graphs
• Coflow polyhedra
• Temporal starvation in multi-channel CSMA networks: an analytical framework

This page was built for publication: A min-max relation for the partial q-colourings of a graph. II: Box perfection

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