Size, chromatic number, and connectivity
type: Item
instance of: scholarly article
title: Size, chromatic number, and connectivity
zbMATH Open document ID: 0817.05026
DOI: 10.1007/BF02986667
author: Tariq Samad
author: Douglas B. West
author: Jayaram Bhasker
published in: Graphs and Combinatorics
publication date: 1995-08-06T00:00:00Z
review text: Let \(g(n,k,c)\) denote the minimum number of edges in a \(k\)-edge-connected graph having order \(n\) and chromatic number at least \(c\) (\(n> k\), \(n\geq c\)). A graph is vertex -- \(c\)-critical if \(\chi(G)= c\) and \(\chi(G- v)= c-1\) for every \(v\in V(G)\); \(G\) is \(c\)-critical if it is vertex -- \(c\)- critical and also \(\chi(G- e)= c-1\) for every \(e\in E(G)\). Theorem 1. Every connected \(c\)-chromatic \(n\)-vertex graph has at least \((\begin{smallmatrix} c\\ 2\end{smallmatrix})+ n- c\) edges, and this is best possible. Theorem 2. If \(n> c> k\geq 3\), then \(g(n, k,c)\geq (\begin{smallmatrix} c\\ 2\end{smallmatrix})+ \lceil\frac{(n+ 1-c)}2\rceil\), except \(g(n,k,c)= (\begin{smallmatrix} c\\ 2\end{smallmatrix})+ \frac{(n+1- c)} 2-1\) if \(c= k+1\), and there is a \(c\)-critical \(n\)-vertex graph with \(\frac{(c- 1)(n+1)} 2- 1\) edges. Theorem 3. If \(n\geq c+k\) and \(c\geq k\geq 2\), then \(g(n,k, c)\leq (\begin{smallmatrix} c\\ 2\end{smallmatrix})+ \lceil \frac{k(n+ 1- c)}2\rceil\). Theorem 4. If \(c\leq \lceil\frac{k+ 1}2\rceil\), or if \(c\leq k\) and \(n> k+ c\), then \(g(n,k,c)= \lceil\frac{kn} 2\rceil\).
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 05C40
Mathematics Subject Classification ID: 05C35
zbMATH DE Number: 700934
zbMATH Keywords: size
zbMATH Keywords: connectivity
zbMATH Keywords: chromatic number
reviewed by: William G. Brown
MaRDI profile type: Publication
cites work: Q3097395
cites work: The structure of k-chromatic graphs
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: THE MAXIMUM CONNECTIVITY OF A GRAPH
cites work: Q5613119
full work available at URL: https://doi.org/10.1007/bf02986667
OpenAlex ID: W1968076455
description: scientific article; zbMATH DE number 700934