Size, chromatic number, and connectivity (Q1340118): Difference between revisions
From MaRDI portal
ReferenceBot (talk | contribs) Changed an Item |
Set OpenAlex properties. |
||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1007/bf02986667 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W1968076455 / rank | |||
Normal rank |
Latest revision as of 08:27, 30 July 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Size, chromatic number, and connectivity |
scientific article |
Statements
Size, chromatic number, and connectivity (English)
0 references
6 August 1995
0 references
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\).
0 references
size
0 references
connectivity
0 references
chromatic number
0 references