Results 1 to 10 of about 45,644 (162)
A Different Short Proof of Brooks’ Theorem
Discussiones Mathematicae Graph Theory, 2014 Lovász gave a short proof of Brooks’ theorem by coloring greedily in a good order. We give a different short proof by reducing to the cubic case.
Rabern Landon
doaj +4 more sources
A unified proof of Brooks' theorem and Catlin's theorem [PDF]
Discrete Mathematics, 2014 We give a new proof of Brooks' theorem that immediately implies a strengthening of Brooks' theorem, known as Catlin's theorem.Comment: Proof rewritten based on referee's ...
Sivaraman, Vaidy
core +4 more sources
BROOKS’ THEOREM FOR MEASURABLE COLORINGS [PDF]
Forum of Mathematics, Sigma, 2016 We generalize Brooks’ theorem to show that if $G$ is a Borel graph on a standard Borel space $
CLINTON T. CONLEY +2 more
doaj +4 more sources
Fast Distributed Brooks' Theorem [PDF]
, 2022 We give a randomized $Δ$-coloring algorithm in the LOCAL model that runs in $\text{poly} \log \log n$ rounds, where $n$ is the number of nodes of the input graph and $Δ$ is its maximum degree. This means that randomized $Δ$-coloring is a rare distributed coloring problem with an upper and lower bound in the same ballpark, $\text{poly}\log\log n$, given
Manuela Fischer +2 more
openalex +3 more sources
Four proofs of the directed Brooks' Theorem [PDF]
Discrete Mathematics, 2022 15 ...
Pierre Aboulker, Guillaume Aubian
openalex +5 more sources
Brooks' theorem on powers of graphs [PDF]
Discrete Mathematics, 2013 We prove that for $k\geq 3$, the bound given by Brooks' theorem on the chromatic number of $k$-th powers of graphs of maximum degree $\Delta \geq 3$ can be lowered by 1, even in the case of online list coloring.Comment: 7 pages, no figure ...
Bonamy, Marthe, Bousquet, Nicolas
core +6 more sources
No Quantum Brooks' Theorem [PDF]
, 2014 First, I introduce quantum graph theory. I also discuss a known lower bound on the independence numbers and derive from it an upper bound on the chromatic numbers of quantum graphs. Then, I construct a family of quantum graphs that can be described as tropical, cyclical, and commutative.
Steven Lu
openalex +4 more sources
On Dirac's Generalization of Brooks' Theorem [PDF]
Canadian Journal of Mathematics, 1972 It is easy to verify that any connected graph G with maximum degree s has chromatic number χ(G) ≦ 1 + s. In [1], R. L. Brooks proved that χ(G) ≦ s, unless s = 2 and G is an odd cycle or s > 2 and G is the complete graph Ks+
Hudson V. Kronk, John Mitchem
openalex +3 more sources
Brooks' Theorem in Graph Streams: A Single-Pass Semi-Streaming Algorithm for $\Delta$-Coloring [PDF]
TheoretiCS, 2023 Every graph with maximum degree $\Delta$ can be colored with $(\Delta+1)$ colors using a simple greedy algorithm. Remarkably, recent work has shown that one can find such a coloring even in the semi-streaming model.
Sepehr Assadi +2 more
doaj +3 more sources