On Brooks' Theorem for Sparse Graphs
From MaRDI portal
Publication:4852428
DOI10.1017/S0963548300001528zbMath0833.05030MaRDI QIDQ4852428
Publication date: 11 March 1996
Published in: Combinatorics, Probability and Computing (Search for Journal in Brave)
Related Items (37)
The \(m\)-degenerate chromatic number of a digraph ⋮ Waiter-Client and Client-Waiter planarity, colorability and minor games ⋮ Colouring graphs with forbidden bipartite subgraphs ⋮ Random lifts of graphs: Independence and chromatic number ⋮ Concentration of non‐Lipschitz functions and applications ⋮ The list chromatic number of graphs with small clique number ⋮ List coloring triangle-free hypergraphs ⋮ Fractional v. integral covers in hypergraphs of bounded edge size ⋮ Bounding \(\chi\) by a fraction of \(\Delta\) for graphs without large cliques ⋮ On the Lovász Theta Function for Independent Sets in Sparse Graphs ⋮ New upper bounds for the chromatic number of a graph ⋮ Probabilistic constructions in generalized quadrangles ⋮ A sequential algorithm for generating random graphs ⋮ Adaptable and conflict colouring multigraphs with no cycles of length three or four ⋮ Efficiently list‐edge coloring multigraphs asymptotically optimally ⋮ The Ramsey number R(3, t) has order of magnitude t2/log t ⋮ Graph and hypergraph colouring via nibble methods: a survey ⋮ A proof of the Erdős-Faber-Lovász conjecture ⋮ Distributed algorithms, the Lovász local lemma, and descriptive combinatorics ⋮ Extremal problems in hypergraph colourings ⋮ A Stronger Bound for the Strong Chromatic Index ⋮ On triangle-free list assignments ⋮ On the Method of Typical Bounded Differences ⋮ Unnamed Item ⋮ Tail bound for the minimal spanning tree of a complete graph. ⋮ Randomly colouring graphs (a combinatorial view) ⋮ Unnamed Item ⋮ Torpid mixing of the Wang-Swendsen-Kotecký algorithm for sampling colorings ⋮ The strong chromatic index ofC4-free graphs ⋮ Coloring H-free hypergraphs ⋮ Algorithmic bounds for the chromatic number† ⋮ On some simple degree conditions that guarantee the upper bound on the chromatic (choice) number of random graphs ⋮ On the chromatic number of simple triangle-free triple systems ⋮ Coloring Sparse Hypergraphs ⋮ Measurable versions of the Lovász local lemma and measurable graph colorings ⋮ Distributed coloring algorithms for triangle-free graphs ⋮ On coupon colorings of graphs
Cites Work
- Asymptotic behavior of the chromatic index for hypergraphs
- A note on the independence number of triangle-free graphs
- On a packing and covering problem
- Near perfect coverings in graphs and hypergraphs
- Sharp concentration of the chromatic number on random graphs \(G_{n,p}\)
- A note on Ramsey numbers
- A dense infinite Sidon sequence
- A note on the independence number of triangle-free graphs. II
- On an upper bound of the graph's chromatic number, depending on the graph's degree and density
- Covering the vertex set of a graph with subgraphs of smaller degree
- A bound on the chromatic number of a graph
- Asymptotic lower bounds for Ramsey functions
- Chromatic number, girth and maximal degree
- Matchings and covers in hypergraphs
- A Lower Bound for Heilbronn'S Problem
This page was built for publication: On Brooks' Theorem for Sparse Graphs
