On the edge-density of 4-critical graphs
type: Item
instance of: scholarly article
title: On the edge-density of 4-critical graphs
zbMATH Open document ID: 1224.05170
author: Babak Farzad
author: Michael Molloy
published in: Combinatorica
publication date: 2011-02-08T00:00:00Z
review text: A graph \(G\) is called critical if, for all proper subgraphs \(H\) of \(G\), the chromatic number of \(H\) is less than the chromatic number of \(G\); it is called \(k\)-critical if it is critical and its chromatic number is \(k\). For \(k\geq 4\), \textit{T. Gallai} [Publ. Math. Inst. Hung. Acad. Sci., Ser. A 8, 165--192 (1963; Zbl 0121.18401)] conjectured that every \(k\)-critical graph with \(n\) vertices has at least \(\frac{k-1}{2}n+\frac{(k-3)(n-k)}{2(k-1)}\) edges. The low-vertex subgraph of a \(k\)-critical graph is the subgraph induced by the vertices of minimum degree, i.e., the vertices of degree \(k-1\). The authors prove Gallai's conjecture for \(4\)-critical graphs whose low-vertex subgraph is connected: Every \(n\)-vertex \(4\)-critical graph in which the subgraph induced by vertices of degree \(3\) is connected has at least \(\frac{5}{3}n-\frac{2}{3}\) edges.
reviewed by: Van Bang Le
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 05C35
Mathematics Subject Classification ID: 05C42
zbMATH DE Number: 5848571
zbMATH Keywords: graph colouring
zbMATH Keywords: critical graph
zbMATH Keywords: edge-density
zbMATH Keywords: Gallai's conjecture
MaRDI profile type: Publication
full work available at URL: s00493-009-2267-y
OpenAlex ID: W2065653857
cites work: A Theorem of R. L. Brooks and a Conjecture of H. Hadwiger
cites work: The number of edges in critical graphs.
cites work: Q5732334
cites work: Q4857375
cites work: On Dirac's Generalization of Brooks' Theorem
cites work: An improved bound on the minimal number of edges in color-critical graphs
cites work: Colour-critical graphs with few edges
cites work: Q4250145
cites work: A new lower bound on the number of edges in colour-critical graphs and hypergraphs
cites work: A new proof of a theorem of Dirac on the number of edges in critical graphs.
cites work: Proof of a conjecture of T. Gallai concerning connectivity properties of colour-critical graphs
cites work: Excess in critical graphs
DOI: 10.1007/S00493-009-2267-Y
Recommended article: The edge density of 4-critical planar graphs
Recommended article: The edge-density of 4-critical planar graphs
Recommended article: On 4-critical planar graphs with high edge density
Recommended article: A density bound for triangle‐free 4‐critical graphs
Recommended article: On the Number of 4-Edge Paths in Graphs With Given Edge Density
Recommended article: On the Minimum Edge‐Density of 4‐Critical Graphs of Girth Five
Recommended article: The edge density of critical digraphs
Recommended article: A note on the size of edge-chromatic 4-critical graphs
Recommended article: A class of edge critical 4-chromatic graphs
Recommended article: On the size of edge-coloring critical graphs with maximum degree 4
description: scientific article; zbMATH DE number 5848571