4-chromatic graphs with large odd girth
type: Item
instance of: scholarly article
title: 4-chromatic graphs with large odd girth
zbMATH Open document ID: 0819.05025
DOI: 10.1016/0012-365X(94)00221-4
author: Nguyen Van Ngoc
author: Zsolt Tuza
published in: Discrete Mathematics
publication date: 1995-08-27T00:00:00Z
review text: For every \(s\geq 1\) and \(t\geq 1\), the graph \(G_{s,t}\) of order \(2st+ t+ 1\) and size \(4st+ 2t\), without short odd cycles is constructed. The authors provide a new purely combinatorial and self-contained proof that the graphs \(G_{s,t}\) are critically 4-chromatic. For \(s\geq 2\) and \(t= 2\) one gets the well-known triangle-free Mycielski graph.
Mathematics Subject Classification ID: 05C15
zbMATH DE Number: 744030
zbMATH Keywords: 4-chromatic graphs
zbMATH Keywords: girth
zbMATH Keywords: Mycielski graph
reviewed by: Jozef Fiamčík
MaRDI profile type: Publication
cites work: Q5532260
cites work: Q5732334
cites work: On coloring graphs with locally small chromatic number
cites work: Kneser's conjecture, chromatic number, and homotopy
cites work: Sur le coloriage des graphs
cites work: On color critical graphs
cites work: On constructive methods in the theory of colour-critical graphs
cites work: Graph coloring in linear time
Recommended article: Odd 4‐edge‐colorability of graphs
Recommended article: Q4856333
Recommended article: Totally odd \(K_4\)-subdivisions in 4-chromatic graphs
Recommended article: Coloring graphs with no \(\text{odd-}K_4\)
Recommended article: 4-chromatic edge critical Grötzsch-Sachs graphs
Recommended article: Q5191333
Recommended article: Topologically 4‐chromatic graphs and signatures of odd cycles
Recommended article: Short odd cycles in 4-chromatic graphs
Recommended article: Diameter of 4-colourable graphs
Recommended article: 4-chromatic Koester graphs
description: scientific article; zbMATH DE number 744030