Coloring square-free Berge graphs

Maria Chudnovsky; Irene Lo; Frédéric Maffray; Nicolas Trotignon; Kristina Vušković

doi:10.1016/j.jctb.2018.07.010

Coloring square-free Berge graphs

Maria Chudnovsky, Irene Lo, Frédéric Maffray, Nicolas Trotignon, Kristina Vušković

Mathematics

Research output: Contribution to journal › Article › peer-review

1 Scopus citations

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.

Original language	English (US)
Pages (from-to)	96-128
Number of pages	33
Journal	Journal of Combinatorial Theory. Series B
Volume	135
DOIs	https://doi.org/10.1016/j.jctb.2018.07.010
State	Published - Mar 2019

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Discrete Mathematics and Combinatorics
Computational Theory and Mathematics

Keywords

Algorithm
Berge graph
Coloring
Square-free

Access to Document

10.1016/j.jctb.2018.07.010

Cite this

@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 = "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.",

}

TY - JOUR

T1 - Coloring square-free Berge graphs

AU - Chudnovsky, Maria

AU - Lo, Irene

AU - Maffray, Frédéric

AU - Trotignon, Nicolas

AU - Vušković, Kristina

PY - 2019/3

Y1 - 2019/3

N2 - 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.

AB - 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.

KW - Algorithm

KW - Berge graph

KW - Coloring

KW - Square-free

UR - http://www.scopus.com/inward/record.url?scp=85052893550&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85052893550&partnerID=8YFLogxK

U2 - 10.1016/j.jctb.2018.07.010

DO - 10.1016/j.jctb.2018.07.010

M3 - Article

AN - SCOPUS:85052893550

SN - 0095-8956

VL - 135

SP - 96

EP - 128

JO - Journal of Combinatorial Theory. Series B

JF - Journal of Combinatorial Theory. Series B

ER -

Coloring square-free Berge graphs

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this