Multicoloring and Mycielski construction
type: Item
instance of: scholarly article
title: Multicoloring and Mycielski construction
zbMATH Open document ID: 1162.05022
author: Wensong Lin
published in: Discrete Mathematics
publication date: 2008-07-11T00:00:00Z
review text: A \(k\)-tuple colouring of a graph \(G\) is an assignment of \(k\) distinct colours to each vertex of \(G\) so that adjacent vertices receive no colours in common. The \(k\)th chromatic number \(\chi_k(G)\) is the smallest number of colours such that \(G\) has a \(k\)-tuple colouring. In the present paper the \(k\)th chromatic number of Mycielskians of graphs (also known as cones over graphs) and of generalized Mycielskians of graphs are studied. Lower and upper bounds are given. Moreover, the fractional chromatic number of graphs \(\chi_f(G)\) of a graph \(G\) is considered. That is the infimum of all fractions \(a/b\) such that \(G\) each vertex of \(G\) is assigned a \(b\)-element subset of \(\{1,2,\dots,a\}\) in such a way that adjacent vertices are assigned disjoint subsets. Especially, \(a/b\)-colourings of generalized Mycielskians of graphs are investigated.
reviewed by: Ulrike Baumann
Mathematics Subject Classification ID: 05C15
zbMATH DE Number: 5300676
zbMATH Keywords: \(k\)-tuple coloring
zbMATH Keywords: \(a/b\)-coloring
zbMATH Keywords: fractional chromatic number
zbMATH Keywords: homomorphism
zbMATH Keywords: Mycielskian
zbMATH Keywords: \(p\)-Mycielskian
zbMATH Keywords: Kneser graph
MaRDI profile type: Publication
full work available at URL: j.disc.2007.07.015
OpenAlex ID: W2015307128
cites work: A lower bound on the chromatic number of Mycielski graphs
cites work: Circular chromatic numbers of Mycielski's graphs
cites work: Two Results Concerning Multicoloring
cites work: Circular chromatic number and Mycielski graphs
cites work: Fractional colorings with large denominators
cites work: Q4390720
cites work: Hamiltonicity, diameter, domination, packing, and biclique partitions of Mycielski's graphs
cites work: Star-extremal graphs and the lexicographic product
cites work: Q2716030
cites work: The circular chromatic number of the Mycielskian ofGdk
cites work: Circular chromatic number of subgraphs
cites work: Multichromatic numbers, star chromatic numbers and Kneser graphs
cites work: On the fractional chromatic number and the lexicographic product of graphs
cites work: Circular chromatic number and a generalization of the construction of Mycielski.
cites work: The fractional chromatic number of mycielski's graphs
cites work: Q5435096
cites work: Several parameters of generalized Mycielskians
cites work: Circular chromatic number for iterated Mycielski graphs
cites work: Sur le coloriage des graphs
cites work: n-tuple colorings and associated graphs
cites work: Fractional chromatic numbers of cones over graphs
DOI: 10.1016/J.DISC.2007.07.015
description: scientific article; zbMATH DE number 5300676