Premium
Coloring Graphs with Dense Neighborhoods
Author(s) -
Rabern Landon
Publication year - 2014
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.21768
Subject(s) - combinatorics , mathematics , degree (music) , vertex (graph theory) , split graph , clique graph , induced subgraph , graph , discrete mathematics , independent set , upper and lower bounds , clique number , block graph , clique , chordal graph , line graph , graph power , 1 planar graph , mathematical analysis , physics , acoustics
It is shown that any graph with maximum degree Δ in which the average degree of the induced subgraph on the set of all neighbors of each vertex exceeds6 k 26 k 2 + 1 Δ + k + 6 is either ( Δ − k ) ‐colorable or contains a clique on more than Δ − 2 k vertices. In the k = 1 case we improve the bound on the average degree to2 3 Δ + 4 and the bound on the clique number to Δ − 1 . As corollaries, we show that every graph satisfies χ ≤ max { ω , Δ − 1 , 4 α } and every graph satisfies χ ≤ max { ω , Δ − 1 , ⌈ 15 + 48 n + 734 ⌉ } .