A note on Reed's Conjecture about ωω, ΔΔ and χχ with respect to vertices of high degree

preprint2016arXivOpen access

Abstract

Reed conjectured that for every graph, χ≤⌈Δ+ω+12⌉χ\leq \left \lceil \frac{Δ+ ω+ 1}{2} \right \rceil holds, where χχ, ωω and ΔΔ denote the chromatic number, clique number and maximum degree of the graph, respectively. We develop an algorithm which takes a hypothetical counterexample as input. The output discloses some hidden structures closely related to high vertex degrees. Consequently, we deduce two graph classes where Reed's Conjecture holds: One contains all graphs in which the vertices of degree at least 55 form a stable set. The other contains all graphs in which every induced cycle of odd length contains a vertex of at most degree 3.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.