Minimax relations for the partial q-colorings of a graph

DOI10.1016/0012-365X(89)90193-3zbMath0685.05021DBLPjournals/dm/Berge89OpenAlexW1977563107WikidataQ56001748 ScholiaQ56001748MaRDI QIDQ1825878

No author found.

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)90193-3

zbMATH Keywords

hypergraphschromatic numberperfect graphminimax relationscartesian sumclique-familypartial q-coloring

Mathematics Subject Classification ID

Hypergraphs (05C65) Coloring of graphs and hypergraphs (05C15)

Related Items (19)

Fair Packing of Independent Sets ⋮ A new polynomial-time algorithm for the maximum weighted (?(G) ? 1)-coloring problem in comparability graphs ⋮ Balanced \(0,\pm 1\)-matrices, bicoloring and total dual integrality ⋮ Embedding a sequential procedure within an evolutionary algorithm for coloring problems in graphs ⋮ Fair allocation algorithms for indivisible items under structured conflict constraints ⋮ On the \(\alpha \)-spectra of uniform hypergraphs and its associated graphs ⋮ Fair allocation of indivisible items with conflict graphs ⋮ Graph covers using \(t\)-colourable vertex sets. ⋮ The maximum vertex coverage problem on bipartite graphs ⋮ INSTANTIAL NEIGHBOURHOOD LOGIC ⋮ Largest \(H\)-eigenvalue of uniform \(s\)-hypertrees ⋮ Bounds on generalized FR codes using hypergraphs ⋮ A min-max relation for the partial q-colourings of a graph. II: Box perfection ⋮ Optimisation and hypergraph theory ⋮ On minimal forbidden subgraph characterizations of balanced graphs ⋮ On the hardness of allocating frequencies for hybrid networks ⋮ Decomposition of balanced matrices ⋮ Temporal starvation in multi-channel CSMA networks: an analytical framework ⋮ Clique partitioning with value-monotone submodular cost

Cites Work

• Coloring perfect \((K_ 4\)-e)-free graphs
• Strong versions of Sperner's theorem
• Perfect product graphs
• On partitions of a partially ordered set
• On perfectness of sums of graphs
• Normal hypergraphs and the perfect graph conjecture
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Minimax relations for the partial q-colorings of a graph