On the chromatic number of a subgraph of the Kneser graph

Bart Litjens; Sven C. Polak; Bart Sevenster; Lluís Vena

doi:10.1016/j.endm.2018.06.039

On the chromatic number of a subgraph of the Kneser graph

Bart Litjens
, Sven C. Polak
, Bart Sevenster
, Lluís Vena

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Scientific › peer-review

47 Downloads (Pure)

Abstract

Let n and k be positive integers with n ≥ 2k. Consider a circle C with n points 1,
...,n in clockwise order. The interlacing graph IGn,k is the graph with vertices
corresponding to k-subsets of [n] that do not contain two adjacent points on C,
and edges between k-subsets P and Q if they interlace: after removing the points
in P from C, the points in Q are in different connected components. In this paper
we prove that the circular chromatic number of IGn,k is equal to n/k, hence the
chromatic number is n/k, and that its independence number is n−k−1
k−1.

Original language	English
Title of host publication	Electronic Notes in Discrete Mathematics
Subtitle of host publication	Discrete Mathematics Days 2018
Editors	Delia Garijo, Alberto Marquez, Oriol Serra
Publisher	Elsevier
Pages	227-232
Number of pages	6
Volume	68
DOIs	https://doi.org/10.1016/j.endm.2018.06.039
Publication status	Published - 2018
Externally published	Yes

Publication series

Name	Electronic Notes in Discrete Mathematics
Publisher	Elsevier
Volume	68
ISSN (Print)	1571-0653

Keywords

Kneser graph
chromatic number
circular chromatic number
independence number
polygon
interlace

Access to Document

10.1016/j.endm.2018.06.039

1-s2.0-S1571065318301306-mainFinal published version, 194 KBLicence: Taverne

Cite this

@inproceedings{32890dc3d8844c99bb127ec1b7541e5c,

title = "On the chromatic number of a subgraph of the Kneser graph",

abstract = "Let n and k be positive integers with n ≥ 2k. Consider a circle C with n points 1, ...,n in clockwise order. The interlacing graph IGn,k is the graph with vertices corresponding to k-subsets of [n] that do not contain two adjacent points on C, and edges between k-subsets P and Q if they interlace: after removing the points in P from C, the points in Q are in different connected components. In this paper we prove that the circular chromatic number of IGn,k is equal to n/k, hence the chromatic number is n/k, and that its independence number is n−k−1 k−1.",

keywords = "Kneser graph, chromatic number, circular chromatic number, independence number, polygon, interlace",

author = "Bart Litjens and Polak, \{Sven C.\} and Bart Sevenster and Llu{\'i}s Vena",

note = "DBLP License: DBLP's bibliographic metadata records provided through http://dblp.org/ are distributed under a Creative Commons CC0 1.0 Universal Public Domain Dedication. Although the bibliographic metadata records are provided consistent with CC0 1.0 Dedication, the content described by the metadata records is not. Content may be subject to copyright, rights of privacy, rights of publicity and other restrictions.",

year = "2018",

doi = "10.1016/j.endm.2018.06.039",

language = "English",

volume = "68",

series = "Electronic Notes in Discrete Mathematics",

publisher = "Elsevier",

pages = "227--232",

editor = "Delia Garijo and Marquez, \{Alberto \} and Oriol Serra",

booktitle = "Electronic Notes in Discrete Mathematics",

address = "Netherlands",

}

On the chromatic number of a subgraph of the Kneser graph. / Litjens, Bart; Polak, Sven C.; Sevenster, Bart et al.
Electronic Notes in Discrete Mathematics: Discrete Mathematics Days 2018. ed. / Delia Garijo; Alberto Marquez; Oriol Serra. Vol. 68 Elsevier, 2018. p. 227-232 (Electronic Notes in Discrete Mathematics; Vol. 68).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Scientific › peer-review

TY - GEN

T1 - On the chromatic number of a subgraph of the Kneser graph

AU - Litjens, Bart

AU - Polak, Sven C.

AU - Sevenster, Bart

AU - Vena, Lluís

N1 - DBLP License: DBLP's bibliographic metadata records provided through http://dblp.org/ are distributed under a Creative Commons CC0 1.0 Universal Public Domain Dedication. Although the bibliographic metadata records are provided consistent with CC0 1.0 Dedication, the content described by the metadata records is not. Content may be subject to copyright, rights of privacy, rights of publicity and other restrictions.

PY - 2018

Y1 - 2018

N2 - Let n and k be positive integers with n ≥ 2k. Consider a circle C with n points 1, ...,n in clockwise order. The interlacing graph IGn,k is the graph with vertices corresponding to k-subsets of [n] that do not contain two adjacent points on C, and edges between k-subsets P and Q if they interlace: after removing the points in P from C, the points in Q are in different connected components. In this paper we prove that the circular chromatic number of IGn,k is equal to n/k, hence the chromatic number is n/k, and that its independence number is n−k−1 k−1.

AB - Let n and k be positive integers with n ≥ 2k. Consider a circle C with n points 1, ...,n in clockwise order. The interlacing graph IGn,k is the graph with vertices corresponding to k-subsets of [n] that do not contain two adjacent points on C, and edges between k-subsets P and Q if they interlace: after removing the points in P from C, the points in Q are in different connected components. In this paper we prove that the circular chromatic number of IGn,k is equal to n/k, hence the chromatic number is n/k, and that its independence number is n−k−1 k−1.

KW - Kneser graph

KW - chromatic number

KW - circular chromatic number

KW - independence number

KW - polygon

KW - interlace

U2 - 10.1016/j.endm.2018.06.039

DO - 10.1016/j.endm.2018.06.039

M3 - Conference contribution

VL - 68

T3 - Electronic Notes in Discrete Mathematics

SP - 227

EP - 232

BT - Electronic Notes in Discrete Mathematics

A2 - Garijo, Delia

A2 - Marquez, Alberto

A2 - Serra, Oriol

PB - Elsevier

ER -

On the chromatic number of a subgraph of the Kneser graph

Abstract

Publication series

Keywords

Access to Document

Fingerprint

Cite this