Coloring clean and K4-free circle graphs

Alexandr V. Kostochka; Kevin G. Milans

doi:10.1007/978-1-4614-0110-0_21

Coloring clean and K₄-free circle graphs

Alexandr V. Kostochka, Kevin G. Milans

Mathematics

Research output: Chapter in Book/Report/Conference proceeding › Chapter

Abstract

A circle graph is the intersection graph of chords drawn in a circle. The best-known general upper bound on the chromatic number of circle graphs with clique number k is 50 · 2^k. We prove a stronger bound of 2k-1 for graphs in a simpler subclass of circle graphs, called clean graphs. Based on this result, we prove that the chromatic number of every circle graph with clique number at most 3 is at most 38.

Original language	English (US)
Title of host publication	Thirty Essays on Geometric Graph Theory
Publisher	Springer
Pages	399-414
Number of pages	16
Volume	9781461401100
ISBN (Electronic)	9781461401100
ISBN (Print)	1461401097, 9781461401094
DOIs	https://doi.org/10.1007/978-1-4614-0110-0_21
State	Published - Jul 1 2013

ASJC Scopus subject areas

General Mathematics

Online availability

10.1007/978-1-4614-0110-0_21

Library availability

Discover UIUC Full Text

Cite this

@inbook{7f7018efe5524e6f9e4e71f7fe50cefc,

title = "Coloring clean and K4-free circle graphs",

abstract = "A circle graph is the intersection graph of chords drawn in a circle. The best-known general upper bound on the chromatic number of circle graphs with clique number k is 50 · 2k. We prove a stronger bound of 2k-1 for graphs in a simpler subclass of circle graphs, called clean graphs. Based on this result, we prove that the chromatic number of every circle graph with clique number at most 3 is at most 38.",

author = "Kostochka, {Alexandr V.} and Milans, {Kevin G.}",

note = "Publisher Copyright: {\textcopyright} Springer Science+Business Media New York 2013. All rights are reserved.",

year = "2013",

month = jul,

day = "1",

doi = "10.1007/978-1-4614-0110-0_21",

language = "English (US)",

isbn = "1461401097",

volume = "9781461401100",

pages = "399--414",

booktitle = "Thirty Essays on Geometric Graph Theory",

publisher = "Springer",

address = "Germany",

}

TY - CHAP

T1 - Coloring clean and K4-free circle graphs

AU - Kostochka, Alexandr V.

AU - Milans, Kevin G.

N1 - Publisher Copyright: © Springer Science+Business Media New York 2013. All rights are reserved.

PY - 2013/7/1

Y1 - 2013/7/1

N2 - A circle graph is the intersection graph of chords drawn in a circle. The best-known general upper bound on the chromatic number of circle graphs with clique number k is 50 · 2k. We prove a stronger bound of 2k-1 for graphs in a simpler subclass of circle graphs, called clean graphs. Based on this result, we prove that the chromatic number of every circle graph with clique number at most 3 is at most 38.

AB - A circle graph is the intersection graph of chords drawn in a circle. The best-known general upper bound on the chromatic number of circle graphs with clique number k is 50 · 2k. We prove a stronger bound of 2k-1 for graphs in a simpler subclass of circle graphs, called clean graphs. Based on this result, we prove that the chromatic number of every circle graph with clique number at most 3 is at most 38.

UR - http://www.scopus.com/inward/record.url?scp=84949177373&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84949177373&partnerID=8YFLogxK

U2 - 10.1007/978-1-4614-0110-0_21

DO - 10.1007/978-1-4614-0110-0_21

M3 - Chapter

AN - SCOPUS:84949177373

SN - 1461401097

SN - 9781461401094

VL - 9781461401100

SP - 399

EP - 414

BT - Thirty Essays on Geometric Graph Theory

PB - Springer

ER -