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

2016/11/07 by Vera Weil, Weil, Vera
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #F.2.2 #FOS: Computer and information sciences #FOS: Mathematics #G.2.1 #G.2.2 #Limits and Structures in Graph Theory

paper · pdf · doi:10.48550/arxiv.1611.02063

openalex publication_date 2016/11/07 · openalex created_date 2022/10/01 · openalex updated_date 2026/07/28

Abstract

Reed conjectured that for every graph, \χ \≤ lceil \(\Δ +\n\ω + 1)/(2) rceil holds, where \χ, \ω and \Δ denote\nthe chromatic number, clique number and maximum degree of the graph,\nrespectively. We develop an algorithm which takes a hypothetical counterexample\nas input. The output discloses some hidden structures closely related to high\nvertex degrees. Consequently, we deduce two graph classes where Reed's\nConjecture holds: One contains all graphs in which the vertices of degree at\nleast 5 form a stable set. The other contains all graphs in which every\ninduced cycle of odd length contains a vertex of at most degree 3.\n

Related

• Reed's conjecture on some special classes of graphs
• New upper bounds on the chromatic number of a graph
• Reed's Conjecture on hole expansions
• A superlocal version of Reed's Conjecture
• A note on Reed's conjecture