Claw‐Free Graphs, Skeletal Graphs, and a Stronger Conjecture on ω, Δ, and χ
From MaRDI portal
Publication:4982280
DOI10.1002/jgt.21797zbMath1309.05076arXiv1212.3036OpenAlexW1559782353WikidataQ29031799 ScholiaQ29031799MaRDI QIDQ4982280
Publication date: 24 March 2015
Published in: Journal of Graph Theory (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1212.3036
Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Coloring of graphs and hypergraphs (05C15) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)
Related Items
A Short Proof That χ Can be Bounded ε Away from Δ + 1 toward ω, A note on Reed's conjecture for triangle-free graphs, Colouring squares of claw-free graphs, Colouring Squares of Claw-free Graphs, Corrigendum to: ``A local epsilon version of Reed's conjecture, A local epsilon version of Reed's conjecture
Cites Work
- Unnamed Item
- Unnamed Item
- A superlocal version of Reed's conjecture
- Claw-free graphs. VI: Colouring
- An algorithm for finding homogeneous pairs
- Claw-free graphs. V. Global structure
- Gear composition and the stable set polytope
- Recognizing claw-free perfect graphs
- The strong perfect-graph conjecture is true for \(K_{1,3}\)-free graphs
- A description of claw-free perfect graphs
- A strengthening of Ben Rebea's lemma
- On the NP-completeness of the \(k\)-colorability problem for triangle-free graphs
- An \(0(n^{1.5})\) algorithm to color proper circular arcs
- Claw-free graphs. I: Orientable prismatic graphs
- An upper bound for the chromatic number of line graphs
- Claw-free graphs. II: Non-orientable prismatic graphs
- Coloring quasi-line graphs
- A New Algorithm for the Maximum Weighted Stable Set Problem in Claw-Free Graphs
- Bounding χ in terms of ω and Δ for quasi-line graphs
- A Note On Reed's Conjecture
- Linear-Time Representation Algorithms for Proper Circular-Arc Graphs and Proper Interval Graphs
- The round-up property of the fractional chromatic number for proper circular arc graphs
- A Local Strengthening of Reed's $\omega$, $\Delta$, $\chi$ Conjecture for Quasi-line Graphs
- Paths, Trees, and Flowers
- An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs