Forbidden Subgraphs and 3-Colorings

DOI10.1137/120895834zbMath1305.05075OpenAlexW2006697314MaRDI QIDQ2935268

Tianjun Ye, Xingxing Yu, Bao-Gang Xu, Geng-Hua Fan

Publication date: 22 December 2014

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/3fb235a05fddc2b465dc1039a87982337388f974

zbMATH Keywords

colorings\(\chi\)-boundedVizing bound

Mathematics Subject Classification ID

Structural characterization of families of graphs (05C75) Coloring of graphs and hypergraphs (05C15) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Related Items (6)

Vizing bound for the chromatic number on some graph classes ⋮ On the chromatic number of (\(P_6\), diamond)-free graphs ⋮ Coloring (\(P_5\), kite)-free graphs with small cliques ⋮ A Survey on the Computational Complexity of Coloring Graphs with Forbidden Subgraphs ⋮ Polynomial \(\chi \)-binding functions and forbidden induced subgraphs: a survey ⋮ $(2P_2,K_4)$-Free Graphs are 4-Colorable

This page was built for publication: Forbidden Subgraphs and 3-Colorings