Critical chromatic number and the complexity of perfect packings in graphs

DOI10.1145/1109557.1109651zbMath1192.05053OpenAlexW4252663710MaRDI QIDQ3581594

Daniela Kühn, Deryk Osthus

Publication date: 16 August 2010

Published in: Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm - SODA '06 (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/1109557.1109651

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Coloring of graphs and hypergraphs (05C15)

Related Items (16)

Tilings in vertex ordered graphs ⋮ Dirac-type results for tilings and coverings in ordered graphs ⋮ The minimum degree threshold for perfect graph packings ⋮ A Degree Sequence Strengthening of the Vertex Degree Threshold for a Perfect Matching in 3-Uniform Hypergraphs ⋮ Rainbow spanning structures in graph and hypergraph systems ⋮ A degree sequence version of the Kühn-Osthus tiling theorem ⋮ Combinatorial and computational aspects of graph packing and graph decomposition ⋮ The Complexity of Perfect Packings in Dense Graphs ⋮ Spanning 3-colourable subgraphs of small bandwidth in dense graphs ⋮ Perfect packings with complete graphs minus an edge ⋮ Proof of the bandwidth conjecture of Bollobás and Komlós ⋮ The complexity of perfect matchings and packings in dense hypergraphs ⋮ Tilings in Randomly Perturbed Dense Graphs ⋮ A Degree Sequence Komlós Theorem ⋮ A discrepancy version of the Hajnal–Szemerédi theorem ⋮ TILING DIRECTED GRAPHS WITH TOURNAMENTS

This page was built for publication: Critical chromatic number and the complexity of perfect packings in graphs