A superlocal version of Reed's conjecture

zbMATH Open1305.05074MaRDI QIDQ490262FDOQ490262

Authors Katherine Edwards, Andrew D. King

Publication date 22 January 2015

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

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

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

zbMATH Keywords

graph colouringReed's conjecturefractional colouring

Mathematics Subject Classification ID

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

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.

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 Note On Reed's Conjecture

Cites work

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

Cited in

(6)

• Local superssimplicity and related concepts
• Short fans and the 5/6 bound for line graphs
• A local epsilon version of Reed's conjecture
• Claw-free graphs, skeletal graphs, and a stronger conjecture on \(\omega\), \(\Delta\), and \(\chi\)
• A short proof that \(\chi\) can be bounded \(\epsilon\) away from \(\Delta + 1\) toward \(\omega\)
• 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)