Premium
4‐Coloring P 6 ‐Free Graphs with No Induced 5‐Cycles
Author(s) -
Chudnovsky Maria,
Maceli Peter,
Stacho Juraj,
Zhong Mingxian
Publication year - 2017
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.22025
Subject(s) - mathematics , combinatorics , edge coloring , discrete mathematics , graph , line graph , graph power
We show that the 4‐coloring problem can be solved in polynomial time for graphs with no induced 5‐cycle C 5 and no induced 6‐vertex path P 6