EUVIMEDEUVIMED entdecken
Crossref

Obstructions for Three-Coloring and List Three-Coloring $H$-Free Graphs

Maria Chudnovsky, Jan Goedgebeur, Oliver Schaudt, Mingxian Zhong

SIAM Journal on Discrete Mathematics · 2020-01 · 34 (1) · 431-469

DOI: 10.1137/18m1210290 ↗

Kurz gefasst

Fachartikel in der Zeitschrift SIAM Journal on Discrete Mathematics, online erschienen am 19.02.2020. Verfasst von Maria Chudnovsky und 3 weiteren Autor:innen. Die Arbeit wurde bisher 9-mal zitiert (Crossref) und nennt 24 Literaturangaben. Gefördert von: Army Research Laboratory, Army Research Office, Fonds Wetenschappelijk Onderzoek.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

A graph is $H$-free if it has no induced subgraph isomorphic to $H$. We characterize all graphs $H$ for which there are only finitely many minimal non-3-colorable $H$-free graphs. Such a characterization was previously known only in the case when $H$ is connected. This solves a problem posed by Golovach et al. As a second result, we characterize all graphs $H$ for which there are only finitely many $H$-free minimal obstructions for list 3-colorability.

Förderung

  • Army Research Laboratory
  • Army Research Office
  • Fonds Wetenschappelijk Onderzoek
  • National Science Foundation

Zitieren

APA

Chudnovsky, M., Goedgebeur, J., Schaudt, O., & Zhong, M. (2020). Obstructions for Three-Coloring and List Three-Coloring $H$-Free Graphs. SIAM Journal on Discrete Mathematics, 34(1), 431-469. https://doi.org/10.1137/18m1210290

Vancouver

Chudnovsky M, Goedgebeur J, Schaudt O, Zhong M. Obstructions for Three-Coloring and List Three-Coloring $H$-Free Graphs. SIAM Journal on Discrete Mathematics. 2020;34(1):431-469. doi:10.1137/18m1210290

BibTeX
@article{Chudnovsky2020,
  author = {Chudnovsky, Maria and Goedgebeur, Jan and Schaudt, Oliver and Zhong, Mingxian},
  title = {Obstructions for Three-Coloring and List Three-Coloring $H$-Free Graphs},
  journal = {SIAM Journal on Discrete Mathematics},
  year = {2020},
  volume = {34},
  number = {1},
  pages = {431--469},
  doi = {10.1137/18m1210290}
}
Kostenlos starten →