Advanced search

Browse by subject

Browse by provider

Browse by language

Content Details
Normal View
CIP View

Outerstring graphs are $\chi$-bounded

Rok, Alexandre...

Free

Share this content

Outerstring graphs are $\chi$-bounded by Rok, Alexandre ( Author )

Content Provider	Lemonjar Open Access
Publisher	Australian National University
Publication Date	01-09-2023
Summary	An outerstring graph is an intersection graph of curves that lie in a common half-plane and have one endpoint on the boundary of that half-plane. We prove that the class of outerstring graphs is $\chi$-bounded, which means that their chromatic number is bounded by a function of their clique number. This generalizes a series of previous results on $\chi$-boundedness of outerstring graphs with various additional restrictions on the shape of curves or the number of times the pairs of curves can cross. The assumption that each curve has an endpoint on the boundary of the half-plane is justified by the known fact that triangle-free intersection graphs of straight-line segments can have arbitrarily large chromatic number.
ISBN	-
Item Type	Article
File Type	pdf
File Size	29.34 KB
Language	English
Subjects	-
Unlimited	MYR 0.01
Total read	-
URL	http://arxiv.org/abs/1312.1559

Citation

Review the full bibliography data and make any necessary corrections before using. Always consult your library resources for the exact formatting and punctuation guidelines.

AMA 11th EditionReferences

Rok, Alexandre. Outerstring graphs are $\chi$-bounded. Australian National University. September 01, 2023. Accessed September 08, 2024. https://online.provdatabase.com/cite/22916

APA 7th EditionReferences

Rok, Alexandre. (2023). Outerstring graphs are $\chi$-bounded. Australian National University. https://online.provdatabase.com/cite/22916

Chicago 17th EditionReferences

Rok, Alexandre. Outerstring graphs are $\chi$-bounded. Australian National University. 2023. https://online.provdatabase.com/cite/22916

HarvardReferences

Rok, Alexandre. (2023). Outerstring graphs are $\chi$-bounded. [Online]. Australian National University. Available from: https://online.provdatabase.com/cite/22916. (Accessed 08 September 2024).

Harvard AustraliaReferences

Rok, Alexandre, 2023, Outerstring graphs are $\chi$-bounded, Australian National University, viewed 08 September 2024, <https://online.provdatabase.com/cite/22916>

MLA 9th EditionWorks Cited

Rok, Alexandre. Outerstring graphs are $\chi$-bounded. Australian National University, 2023. PROV Database, https://online.provdatabase.com/cite/22916.

Share this eBook