Colorings of complements of line graphs

Hamid Reza Daneshpajouh, Frédéric Meunier, Guilhem Mizrahi

Research output: Journal PublicationArticlepeer-review

2 Citations (Scopus)


Our purpose is to show that complements of line graphs (of graphs) enjoy nice coloring properties. We show that for all graphs in this class the local and usual chromatic numbers are equal. We also prove a sufficient condition for the chromatic number to be equal to a natural upper bound. A consequence of this latter condition is a complete characterization of all induced subgraphs of the Kneser graph (Formula presented.) that have a chromatic number equal to its chromatic number, namely (Formula presented.). In addition to the upper bound, a lower bound is provided by Dol'nikov's theorem, a classical result of the topological method in graph theory. We prove the NP-hardness of deciding the equality between the chromatic number and any of these bounds. The topological method is especially suitable for the study of coloring properties of complements of line graphs of hypergraphs. Nevertheless, all proofs in this article are elementary and we also provide a short discussion on the ability for the topological methods to cover some of our results.

Original languageEnglish
Pages (from-to)216-233
Number of pages18
JournalJournal of Graph Theory
Issue number2
Publication statusPublished - Sept 2021
Externally publishedYes


  • Kneser graph
  • NP-hardness
  • chromatic number
  • colorability defect
  • line graph
  • local chromatic number

ASJC Scopus subject areas

  • Geometry and Topology
  • Discrete Mathematics and Combinatorics


Dive into the research topics of 'Colorings of complements of line graphs'. Together they form a unique fingerprint.

Cite this