Bounding χ in terms of ω and Δ for quasi-line graphs

DOI10.1002/jgt.20334zbMath1184.05045OpenAlexW4253689634MaRDI QIDQ3605150

Andrew D. King, Bruce A. Reed

Publication date: 20 February 2009

Published in: Journal of Graph Theory (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/jgt.20334

zbMATH Keywords

chromatic numberclique numberquasi-line graphs

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph operations (line graphs, products, etc.) (05C76)

Related Items (18)

List-Coloring Claw-Free Graphs with $\Delta-1$ Colors ⋮ Disconnected cuts in claw-free graphs ⋮ Combinatorics. Abstracts from the workshop held January 1--7, 2023 ⋮ Asymptotics of the chromatic number for quasi-line graphs ⋮ Large cliques in graphs with high chromatic number ⋮ On the recognition of fuzzy circular interval graphs ⋮ The \(k\)-in-a-path problem for claw-free graphs ⋮ A fast algorithm to remove proper and homogeneous pairs of cliques (while preserving some graph invariants) ⋮ Unnamed Item ⋮ Graph coloring approach with new upper bounds for the chromatic number: team building application ⋮ Randomly colouring graphs (a combinatorial view) ⋮ Parameterized complexity of induced graph matching on claw-free graphs ⋮ Domination When the Stars Are Out ⋮ Bounding \(\chi \) in terms of \(\omega \) and \(\varDelta \) for some classes of graphs ⋮ Some results on Reed's conjecture about \(\omega ,\Delta \), and \(\chi \) with respect to \(\alpha \) ⋮ Induced Disjoint Paths in Claw-Free Graphs ⋮ Claw‐Free Graphs, Skeletal Graphs, and a Stronger Conjecture on ω, Δ, and χ ⋮ Solving the Weighted Stable Set Problem in Claw-Free Graphs via Decomposition

Cites Work

• Bisimplicial vertices in even-hole-free graphs
• An O(qn) algorithm to q-color a proper family of circular arcs
• Bull-free Berge graphs are perfect
• A description of claw-free perfect graphs
• Compositions for perfect graphs
• An upper bound for the chromatic number of line graphs
• Coloring quasi-line graphs
• On the $1.1$ Edge-Coloring of Multigraphs
• 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 Theorem on Coloring the Lines of a Network

This page was built for publication: Bounding χ in terms of ω and Δ for quasi-line graphs