Coloring Graphs with Dense Neighborhoods | Zendy

Rabern Landon | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

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 ⌉ } .

This content is not available in your region!

Continue researching here.

Having issues? You can contact us here

Accelerating Research