New Construction of Graphs with High Chromatic Number and Small Clique Number

Hamid Reza Daneshpajouh

doi:10.1007/s00454-017-9934-3

New Construction of Graphs with High Chromatic Number and Small Clique Number

Hamid Reza Daneshpajouh^*

^*Corresponding author for this work

Research output: Journal Publication › Article › peer-review

5 Citations (Scopus)

Abstract

We introduce a new method for constructing graphs with high chromatic number and small clique number. Indeed, we present a new proof for the well-known Kneser conjecture via this method.

Original language	English
Pages (from-to)	238-245
Number of pages	8
Journal	Discrete and Computational Geometry
Volume	59
Issue number	1
DOIs	https://doi.org/10.1007/s00454-017-9934-3
Publication status	Published - 1 Jan 2018
Externally published	Yes

Free Keywords

Borsuk–Ulam theorem
Chromatic number
Triangle-free graphs
Tucker’s lemma

ASJC Scopus subject areas

Theoretical Computer Science
Geometry and Topology
Discrete Mathematics and Combinatorics
Computational Theory and Mathematics

Access to Document

10.1007/s00454-017-9934-3

Cite this

@article{e9f781e6c10b42e0bf2a1b0943e5920b,

title = "New Construction of Graphs with High Chromatic Number and Small Clique Number",

abstract = "We introduce a new method for constructing graphs with high chromatic number and small clique number. Indeed, we present a new proof for the well-known Kneser conjecture via this method.",

keywords = "Borsuk–Ulam theorem, Chromatic number, Triangle-free graphs, Tucker{\textquoteright}s lemma",

author = "Daneshpajouh, \{Hamid Reza\}",

note = "Publisher Copyright: {\textcopyright} 2017, Springer Science+Business Media, LLC.",

year = "2018",

month = jan,

day = "1",

doi = "10.1007/s00454-017-9934-3",

language = "English",

volume = "59",

pages = "238--245",

journal = "Discrete and Computational Geometry",

issn = "0179-5376",

publisher = "Springer New York",

number = "1",

}

TY - JOUR

T1 - New Construction of Graphs with High Chromatic Number and Small Clique Number

AU - Daneshpajouh, Hamid Reza

PY - 2018/1/1

Y1 - 2018/1/1

N2 - We introduce a new method for constructing graphs with high chromatic number and small clique number. Indeed, we present a new proof for the well-known Kneser conjecture via this method.

AB - We introduce a new method for constructing graphs with high chromatic number and small clique number. Indeed, we present a new proof for the well-known Kneser conjecture via this method.

KW - Borsuk–Ulam theorem

KW - Chromatic number

KW - Triangle-free graphs

KW - Tucker’s lemma

UR - https://www.scopus.com/pages/publications/85029766724

U2 - 10.1007/s00454-017-9934-3

DO - 10.1007/s00454-017-9934-3

M3 - Article

AN - SCOPUS:85029766724

SN - 0179-5376

VL - 59

SP - 238

EP - 245

JO - Discrete and Computational Geometry

JF - Discrete and Computational Geometry

IS - 1

ER -

New Construction of Graphs with High Chromatic Number and Small Clique Number

Abstract

Free Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this