Coloring quasi-line graphs

Maria Chudnovsky, Alexandra Ovetsky

Research output: Contribution to journalArticlepeer-review

29 Scopus citations

Abstract

A graph G is a quasi-line graph if for every vertex v, the set of neighbors of v can be expressed as the union of two cliques. The class of quasi-line graphs is a proper superset of the class of line graphs. A theorem of Shannon's implies that if G is a line graph, then it can be properly colored using no more than 3/2ω(G) colors, where ω(G) is the size of the largest clique in G. In this article, we extend this result to all quasi-line graphs. We also Show that this bound is tight.

Original languageEnglish (US)
Pages (from-to)41-50
Number of pages10
JournalJournal of Graph Theory
Volume54
Issue number1
DOIs
StatePublished - Jan 2007

All Science Journal Classification (ASJC) codes

  • Discrete Mathematics and Combinatorics
  • Geometry and Topology

Keywords

  • Claw-free graphs
  • Coloring
  • Quasi-line graphs

Fingerprint

Dive into the research topics of 'Coloring quasi-line graphs'. Together they form a unique fingerprint.

Cite this