@article{458980586611456ca2846aed49f4e420,
title = "Coloring square-free Berge graphs",
abstract = "We consider the class of Berge graphs that do not contain an induced cycle of length four. We present a purely graph-theoretical algorithm that produces an optimal coloring in polynomial time for every graph in that class.",
keywords = "Algorithm, Berge graph, Coloring, Square-free",
author = "Maria Chudnovsky and Irene Lo and Fr{\'e}d{\'e}ric Maffray and Nicolas Trotignon and Kristina Vu{\v s}kovi{\'c}",
note = "Funding Information: Partially supported by NSF grants DMS-1265803 and DMS-1550991. This material is based upon work supported in part by the U.S. Army Research Laboratory and the U.S. Army Research Office under grant number W911NF-16-1-0404.Partially supported by ANR project STINT under reference ANR-13-BS02-0007.Partially supported by ANR project STINT under reference ANR-13-BS02-0007, and by the LABEX MILYON (ANR-10-LABX-0070) of Universit{\'e} de Lyon, within the program “Investissements d'Avenir” (ANR-11-IDEX-0007) operated by the French National Research Agency (ANR).Partially supported by EPSRC grant EP/K016423/1 and Serbian Ministry of Education and Science projects 174033 and III44006. Funding Information: Partially supported by EPSRC grant EP/K016423/1 and Serbian Ministry of Education and Science projects 174033 and III44006. Publisher Copyright: {\textcopyright} 2018 Elsevier Inc.",
year = "2019",
month = mar,
doi = "10.1016/j.jctb.2018.07.010",
language = "English (US)",
volume = "135",
pages = "96--128",
journal = "Journal of Combinatorial Theory. Series B",
issn = "0095-8956",
publisher = "Academic Press Inc.",
}