The strong chromatic number of a graph

DOI10.1002/rsa.3240030102zbMath0751.05034OpenAlexW2146017177WikidataQ56390830 ScholiaQ56390830MaRDI QIDQ3989737

Noga Alon

Publication date: 28 June 1992

Published in: Random Structures & Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/rsa.3240030102

zbMATH Keywords

perfect matchingstrong chromatic numberstrongly \(k\)-colorable

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 (23)

Bounded transversals in multipartite graphs ⋮ Covering with Latin transversals ⋮ An algorithmic approach to the Lovász local lemma. I ⋮ A parallel algorithmic version of the local lemma ⋮ Independent transversals in locally sparse graphs ⋮ Choice Numbers of Graphs: a Probabilistic Approach ⋮ 2-factors in dense graphs ⋮ Independent transversals in \(r\)-partite graphs ⋮ On factors of independent transversals in \(k\)-partite graphs ⋮ An average degree condition for independent transversals ⋮ Newi-Perfect Cycle Decompositions via Vertex Colorings of Graphs ⋮ On finding constrained independent sets in cycles ⋮ Problems and results in extremal combinatorics. I. ⋮ Fractional total colourings of graphs of high girth ⋮ A Note on Degenerate and Spectrally Degenerate Graphs ⋮ Chromatic numbers of layered graphs with a bounded maximal clique ⋮ On monochromatic component size for improper colourings ⋮ Near-optimal list colorings ⋮ Uniform coloring of graph ⋮ An asymptotic bound for the strong chromatic number ⋮ Some results on \((a:b)\)-choosability ⋮ Coloring graphs with sparse neighborhoods ⋮ Probabilistic methods in coloring and decomposition problems

Cites Work

• The linear arboricity of graphs
• A parallel algorithmic version of the local lemma
• Transversals of Vertex Partitions in Graphs

This page was built for publication: The strong chromatic number of a graph