An upper bound for the chromatic number of line graphs

DOI10.1016/J.EJC.2007.04.014zbMATH Open1125.05039OpenAlexW2048900104MaRDI QIDQ2461774FDOQ2461774

Authors: Adrian Vetta, Andrew D. King, Bruce Reed 

Publication date: 21 November 2007

Published in: European Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL: https://hal.inria.fr/hal-01184357/file/dmAE0130.pdf

Recommendations

• An upper bound for the chromatic number of line graphs
• A strengthening of Brooks' Theorem for line graphs
• Bounding χ in terms of ω and Δ for quasi-line graphs
• Some results on Reed's conjecture about \(\omega ,\Delta \), and \(\chi \) with respect to \(\alpha \)
• A Local Strengthening of Reed's $\omega$, $\Delta$, $\chi$ Conjecture for Quasi-line Graphs

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Cites Work

• The NP-Completeness of Edge-Coloring
• Maximum matching and a polyhedron with 0,1-vertices
• Title not available (Why is that?)
• Title not available (Why is that?)
• On Representatives of Subsets
• Asymptotics of the chromatic index for multigraphs
• Improving a family of approximation algorithms to edge color multigraphs
• On the $1.1$ Edge-Coloring of Multigraphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• An Optimal Algorithm to Detect a Line Graph and Output Its Root Graph

Cited In (21)

• Graph coloring approach with new upper bounds for the chromatic number: team building application
• Hitting all maximum cliques with a stable set using lopsided independent transversals
• An upper bound of linear chromatic number of planar graphs
• Short fans and the 5/6 bound for line graphs
• A strengthening of Brooks' Theorem for line graphs
• Chromatic number of \(P_5\)-free graphs: Reed's conjecture
• Algorithmic bounds for the chromatic number†
• Bounding \(\chi \) in terms of \(\omega \) and \(\varDelta \) for some classes of graphs
• Randomly colouring graphs (a combinatorial view)
• An upper bound for the chromatic number of line graphs
• Proof of McDiarmid-Reed conjecture for a subclass of hexagonal graphs
• Title not available (Why is that?)
• A quick way to verify if a graph is 3-colorable
• Linear Bound in Terms of Maxmaxflow for the Chromatic Roots of Series-Parallel Graphs
• On hitting all maximum cliques with an independent set
• A superlocal version of Reed's conjecture
• Claw-free graphs, skeletal graphs, and a stronger conjecture on \(\omega\), \(\Delta\), and \(\chi\)
• Bounding χ in terms of ω and Δ for quasi-line graphs
• A short proof that \(\chi\) can be bounded \(\epsilon\) away from \(\Delta + 1\) toward \(\omega\)
• The \(k\)th upper chromatic number of the line
• Rainbow neighbourhood number of graphs

This page was built for publication: An upper bound for the chromatic number of line graphs

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