A superlocal version of Reed's conjecture

zbMATH Open1305.05074arXiv1208.5188MaRDI QIDQ490262FDOQ490262

Katherine Edwards, Andrew D. King

Publication date: 22 January 2015

Published in: The Electronic Journal of Combinatorics (Search for Journal in Brave)

Abstract: Reed's well-known $omega$, $Delta$, $chi$ conjecture proposes that every graph satisfies $chileqlceilfrac12(Delta+1+omega)ceil$. The second author formulated a {em local strengthening} of this conjecture that considers a bound supplied by the neighbourhood of a single vertex. Following the idea that the chromatic number cannot be greatly affected by any particular stable set of vertices, we propose a further strengthening that considers a bound supplied by the neighbourhoods of two adjacent vertices. We provide some fundamental evidence in support, namely that the stronger bound holds in the fractional relaxation and holds for both quasi-line graphs and graphs with stability number two. We also conjecture that in the fractional version, we can push the locality even further.

Full work available at URL: https://arxiv.org/abs/1208.5188

File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Recommendations

• A Local Strengthening of Reed's $\omega$, $\Delta$, $\chi$ Conjecture for Quasi-line Graphs
• Colouring graphs with sparse neighbourhoods: bounds and applications
• On Reed's conjecture about \(\omega\), \(\Delta\) and \(\chi\)
• A local epsilon version of Reed's conjecture
• A Note On Reed's Conjecture

zbMATH Keywords

graph colouringReed's conjecturefractional colouring

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Fractional graph theory, fuzzy graph theory (05C72)

Cites Work

• Paths, Trees, and Flowers
• Linear-Time Representation Algorithms for Proper Circular-Arc Graphs and Proper Interval Graphs
• The structure of claw-free graphs
• Title not available (Why is that?)
• Graph colouring and the probabilistic method
• An upper bound for the chromatic number of line graphs
• Bounding \(\chi \) in terms of \(\omega \) and \(\varDelta \) for some classes of graphs
• Asymptotics of the chromatic index for multigraphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• Asymptotics of the chromatic number for quasi-line graphs
• The round-up property of the fractional chromatic number for proper circular arc graphs
• Bounding the fractional chromatic number of \(K_\Delta\)-free graphs
• A Local Strengthening of Reed's $\omega$, $\Delta$, $\chi$ Conjecture for Quasi-line Graphs

Cited In (5)

• A Short Proof That χ Can be Bounded ε Away from Δ + 1 toward ω
• Claw‐Free Graphs, Skeletal Graphs, and a Stronger Conjecture on ω, Δ, and χ
• Local superssimplicity and related concepts
• Short Fans and the 5/6 Bound for Line Graphs
• Fractional strong chromatic index of bipartite graphs

This page was built for publication: A superlocal version of Reed's conjecture

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q490262)