On the chromatic number of certain highly symmetric graphs
type: Item
instance of: scholarly article
title: On the chromatic number of certain highly symmetric graphs
zbMATH Open document ID: 0572.05025
DOI: 10.1016/0012-365X(85)90060-3
published in: Discrete Mathematics
publication date: 1985-01-01T00:00:00Z
review text: For \(1\leq k\leq n\) let G(n,k) be the graph whose vertices are the \(n(n- 1)...(n-k+1)\) sequences of k distinct elements from \(\{\) 1,2,...,n\(\}\), two such sequences being joined by an edge if they differ in exactly one place. Let N(n,k) denote the maximum number of classes in a partition of the vertices of G(n,k) such that for every class C, every vertex v and every i, \(1\leq i\leq k\), there is a w in C that differs from v in at most place i. This number N(n,k) and the chromatic number \(\chi\) (n,k) of G(n,k) are investigated. It is proved that \(N(n,k)\leq n-k+11\leq \chi (n,k)\) with equality for certain values of n and k. The problems discussed are related to questions in mathematical logic by \textit{L. Henkin}, \textit{J. D. Monk}, and \textit{A. Tarski}, and \textit{H. Andréka} and \textit{I. Németi} [Cylindric set algebras, Lect. Notes Math. 883 (1981; Zbl 0497.03025)].
Mathematics Subject Classification ID: 05C15
zbMATH DE Number: 3912406
zbMATH Keywords: cylindric set algebras
zbMATH Keywords: symmetric graphs
zbMATH Keywords: chromatic number
author: Péter P. Pálfy
reviewed by: Bjarne Toft
MaRDI profile type: Publication
cites work: Q3258698
cites work: Q3941433
cites work: A note on Hamiltonian split graphs
cites work: Q4083324
cites work: Q4198056
cites work: Q5591387
cites work: Q3760579
Recommended article: On the chromatic number of graphs
Recommended article: The total chromatic number of graphs of even order and high degree
Recommended article: Chromatic symmetric functions and \(H\)-free graphs
Recommended article: On the Generalized $\vartheta$-Number and Related Problems for Highly Symmetric Graphs
Recommended article: Q4242485
Recommended article: Q3480060
Recommended article: Q3180778
Recommended article: The total chromatic number of regular graphs of high degree
Recommended article: On the chromatic number of circulant graphs
Recommended article: Q4838787
description: scientific article; zbMATH DE number 3912406