◍wovepaper
SearchResearchersInstitutions
Sign in
math.COSep 1, 2015
1
citations (OpenAlex)
authors
  • Maria Chudnovsky
  • Irene Lo
  • Frederic Maffray
  • Nicolas Trotignon
  • Kristina Vuskovic
institutions
  • Centre National de la Recherche Scientifique
  • Columbia University
  • École Normale Supérieure de Lyon
  • Laboratoire de l'Informatique du Parallélisme
  • Laboratoire des Sciences pour la Conception, l'Optimisation et la Production
  • Princeton University
  • Union University
  • Université Grenoble Alpes
  • University of Leeds
arXiv abstractPDF
paper

Coloring Square-free Berge Graphs

arXiv:1509.09195 · doi:10.1016/j.jctb.2018.07.010

Abstract

We consider the class of Berge graphs that do not contain a chordless cycle of length 4. We present a purely graph-theoretical algorithm that produces an optimal coloring in polynomial time for every graph in that class.

References in corpus (3)

  • Algorithms for perfectly contractile graphs
  • A class of perfectly contractile graphs
  • Coloring Artemis graphs
◍wovepaper

Papers, researchers and institutions, woven together.

Explore
  • Search
  • Researchers
  • Institutions
Account
  • Library
  • Chat
Data
  • arXiv.org
  • Semantic Scholar
  • OpenAlex
  • Latest RSS
AboutContactPrivacyDevelopersllms.txtopenapi.json
Not affiliated with arXiv. Researcher data from Semantic Scholar (ODC-BY) and OpenAlex.