Chromatic partitions of a graph
type: Item
instance of: scholarly article
title: Chromatic partitions of a graph
zbMATH Open document ID: 0688.05028
DOI: 10.1016/0012-365X(89)90211-2
author: E. Sampathkumar
author: C. V. Venkatachalam
published in: Discrete Mathematics
publication date: 1989-01-01T00:00:00Z
review text: The chromatic partition number \(\chi_ k(G)\) (k\(\geq 1)\) of a graph G is defined to be the minimum number of colours needed in a \(P_ k\)- colouring of G. The following are the main results: (1) For any graph G of order p, \[ \frac{p}{M_ k}\leq \chi_ k(G)\leq \{\frac{p-M_ k}{k}\}+1\quad and\quad -\frac{p}{\beta_ 0k}\leq \chi_ k(G)\leq \{\frac{p-\beta_ k}{k}\}+1, \] where \(M_ k\) is the maximum number of points in a \(P_ k\)-set of G, \(\beta_ 0\) is the independence number of G and \(\{\) \(r\}\) is the least integer not less than r. (2) For any positive integer n, there exists a \(K_{k+2}\)-free graph G with \(\chi_ k(G)=n.\) (3) For \(n\geq 2\), every (k,n)-critical graph is \(n+(k-2)\)-line connected. (4) For any graph G with \(\chi_ k(G)\pm n\geq 2\), \(\chi_ k(G)\leq \max \delta (G^ 1)-k+2\), where the max is taken over all induced subgraphs \(G^ 1\) of G. (5) For any graph G and for any integer \(k\geq 1\), \(\chi_ k(G)\leq 1+[\frac{m(G)}{k}]\), where m(G) is the largest eigenvalue of the adjacency matrix of G.
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 05C75
zbMATH DE Number: 4127231
zbMATH Keywords: general chromatic number
zbMATH Keywords: chromatic partition number
zbMATH Keywords: \(P_ k\)-colouring
zbMATH Keywords: \(P_ k\)-set
reviewed by: I. H. Nagaraja Rao
MaRDI profile type: MaRDI publication profile
cites work: The subchromatic number of a graph
cites work: Q3758854
cites work: Q3941433
cites work: On generalized graph colorings
cites work: Q5560916
cites work: The Point-Arboricity of Planar Graphs
cites work: The point-arboricity of a graph
cites work: An interpolation theorem for partitions which are complete with respect to hereditary properties
cites work: Parallel concepts in graph theory
cites work: Q3220612
cites work: Q5668824
cites work: Q5615946
cites work: k-Degenerate Graphs
cites work: On the Point-Arboricity of a Graph and its Complement
cites work: Q3689206
cites work: On Complementary Graphs
cites work: Q3859786
cites work: Generalizations of independence and chromatic numbers of a graph
cites work: An inequality for the chromatic number of a graph
cites work: On critical subgraphs of colour-critical graphs
cites work: The Eigenvalues of a Graph and Its Chromatic Number
full work available at URL: 0012-365x(89)90211-2
OpenAlex ID: W1964998024
Recommended article: Generalizations of independence and chromatic numbers of a graph
Recommended article: Independent sets in k-chromatic graphs
Recommended article: On the partition and coloring of a graph by cliques
Recommended article: Q5536129
Recommended article: Q3490030
description: scientific article; zbMATH DE number 4127231