Asymptotics of the chromatic number for quasi-line graphs

DOI10.1016/j.endm.2007.07.056zbMath1341.05078arXiv1102.0805OpenAlexW2568525199MaRDI QIDQ3503489

Andrew D. King, Bruce A. Reed

Publication date: 5 June 2008

Published in: Electronic Notes in Discrete Mathematics, Journal of Graph Theory (Search for Journal in Brave)

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

zbMATH Keywords

approximation algorithmgraph coloringfractional chromatic numberchromatic numberchromatic indexquasi-line graphfractional graph coloring

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Approximation algorithms (68W25) Graph operations (line graphs, products, etc.) (05C76)

Related Items (6)

Colouring squares of claw-free graphs ⋮ Coloring fuzzy circular interval graphs ⋮ Colouring Squares of Claw-free Graphs ⋮ A superlocal version of Reed's conjecture ⋮ Solving the Weighted Stable Set Problem in Claw-Free Graphs via Decomposition ⋮ Coloring Fuzzy Circular Interval Graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A fast algorithm to remove proper and homogeneous pairs of cliques (while preserving some graph invariants)
• Claw-free graphs. V. Global structure
• Bull-free Berge graphs are perfect
• Asymptotics of the chromatic index for multigraphs
• On maximal independent sets of vertices in claw-free graphs
• The ellipsoid method and its consequences in combinatorial optimization
• On the ratio of optimal integral and fractional covers
• An \(0(n^{1.5})\) algorithm to color proper circular arcs
• Claw-free graphs. VII. Quasi-line graphs
• Coloring quasi-line graphs
• Hadwiger's conjecture for quasi-line graphs
• Bounding χ in terms of ω and Δ for quasi-line graphs
• The NP-Completeness of Edge-Coloring
• Free Bits, PCPs, and Nonapproximability---Towards Tight Results
• A REVISION OF MINTY'S ALGORITHM FOR FINDING A MAXIMUM WEIGHT STABLE SET OF A CLAW-FREE GRAPH
• 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

This page was built for publication: Asymptotics of the chromatic number for quasi-line graphs