Coloring of distance graphs with intervals as distance sets

DOI10.1016/J.EJC.2004.01.017MaRDI QIDQ2567207zbMATH OpenOpenAlexFDO

Authors P. C. B. Lam, Wensong Lin

Publication date 29 September 2005

Published in European Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ejc.2004.01.017

zbMATH Keywords

Chromatic number Circular chromatic number Fractional chromatic number

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Review text

The distance graph \(G(\mathbb Z,D)\) has vertex set \(\mathbb Z\) and two vertices \(x\) and \(y\) are adjacent if and only if their distance \(d(x,y)=| x-y| \) is an element of the so-called distance set \(D \subseteq \mathbb N\). The authors investigate the chromatic number, the fractional chromatic number and the circular chromatic number of distance graphs \(G(\mathbb Z,D)\) with distance sets \(D=D_{m,[k,k']}=\{1,2,\dots,m\}-\{k,k+1,\dots,k'\}\). A circular coloring of a graph \(G\) is a generalization of a vertex coloring and is defined as an assignment \(c\) of open unit length arcs of a circle \(C\) to the vertices of \(G\) such that \(c(x)\cap c(y)=\emptyset\) whenever the vertices \(x\) and \(y\) are adjacent. In particular, the chromatic number of \(G(\mathbb Z,D_{m,[2,k']})\) is completely determined in this paper.

Recommendations

Cites work

Cited in

(23)

This page was built for publication: Coloring of distance graphs with intervals as distance sets

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2567207)