3-colorable subclasses OF P8-FREE GRAPHS∗

Maria Chudnovsky; Juraj Stacho

doi:10.1137/16M1104858

3-colorable subclasses OF P₈-FREE GRAPHS^∗

Maria Chudnovsky, Juraj Stacho

Mathematics

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

7 Scopus citations

Abstract

In this paper, we study 3-colorable graphs having no induced 8-vertex path and no induced cycles of specific lengths. We prove a characterization by critical graphs in three particular cases.

Original language	English (US)
Pages (from-to)	1111-1138
Number of pages	28
Journal	SIAM Journal on Discrete Mathematics
Volume	32
Issue number	2
DOIs	https://doi.org/10.1137/16M1104858
State	Published - 2018

All Science Journal Classification (ASJC) codes

General Mathematics

Keywords

Coloring
Forbidden induced subgraphs
Induced paths

Access to Document

10.1137/16M1104858

Cite this

@article{9bb6acd7e7ca470c9d5d3bc0cf4133a9,

title = "3-colorable subclasses OF P8-FREE GRAPHS∗ ",

abstract = "In this paper, we study 3-colorable graphs having no induced 8-vertex path and no induced cycles of specific lengths. We prove a characterization by critical graphs in three particular cases.",

keywords = "Coloring, Forbidden induced subgraphs, Induced paths",

author = "Maria Chudnovsky and Juraj Stacho",

note = "Publisher Copyright: {\textcopyright} 2018 Society for Industrial and Applied Mathematics.",

year = "2018",

doi = "10.1137/16M1104858",

language = "English (US)",

volume = "32",

pages = "1111--1138",

journal = "SIAM Journal on Discrete Mathematics",

issn = "0895-4801",

publisher = "Society for Industrial and Applied Mathematics Publications",

number = "2",

}

TY - JOUR

T1 - 3-colorable subclasses OF P8-FREE GRAPHS∗

AU - Chudnovsky, Maria

AU - Stacho, Juraj

PY - 2018

Y1 - 2018

N2 - In this paper, we study 3-colorable graphs having no induced 8-vertex path and no induced cycles of specific lengths. We prove a characterization by critical graphs in three particular cases.

AB - In this paper, we study 3-colorable graphs having no induced 8-vertex path and no induced cycles of specific lengths. We prove a characterization by critical graphs in three particular cases.

KW - Coloring

KW - Forbidden induced subgraphs

KW - Induced paths

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

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

U2 - 10.1137/16M1104858

DO - 10.1137/16M1104858

M3 - Article

AN - SCOPUS:85049556702

SN - 0895-4801

VL - 32

SP - 1111

EP - 1138

JO - SIAM Journal on Discrete Mathematics

JF - SIAM Journal on Discrete Mathematics

IS - 2

ER -