Universal Sets for Straight-Line Embeddings of Bicolored Graphs

Josef Cibulka (), Jan Kynčl (), Viola Mészáros (), Rudolf Stolař () and Pavel Valtr
Additional contact information
Josef Cibulka: Charles University, Department of Applied Mathematics
Jan Kynčl: Charles University, Department of Applied Mathematics and Institute for Theoretical Computer Science
Viola Mészáros: Charles University, Department of Applied Mathematics and Institute for Theoretical Computer Science
Rudolf Stolař: Charles University, Department of Applied Mathematics
Pavel Valtr: Charles University, Department of Applied Mathematics and Institute for Theoretical Computer Science

A chapter in Thirty Essays on Geometric Graph Theory, 2013, pp 101-119 from Springer

Abstract: Abstract A set S of n points is 2-color universal for a graph G on n vertices if, for every proper 2-coloring of G and for every 2-coloring of S with the same sizes of color classes as G, G is straight-line embeddable on S. We show that the so-called double-chain is 2-color universal for paths if each of the two chains contains at least one fifth of all the points, but not if one of the chains is more than approximately 28 times longer than the other. A 2-coloring of G is equitable if the sizes of the color classes differ by at most 1. A bipartite graph is equitable if it admits an equitable proper coloring. We study the case when S is the double-chain with chain sizes differing by at most 1 and G is an equitable bipartite graph. We prove that this S is not 2-color universal if G is not a forest of caterpillars and that it is 2-color universal for equitable caterpillars with at most one half nonleaf vertices. We also show that if this S is equitably 2-colored, then equitably properly 2-colored forests of stars can be embedded on it.

Keywords: Bipartite Graph; Color Classis; Geometric Graph; Outerplanar Graph; White Point (search for similar items in EconPapers)
Date: 2013
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:sprchp:978-1-4614-0110-0_8

Ordering information: This item can be ordered from
http://www.springer.com/9781461401100

DOI: 10.1007/978-1-4614-0110-0_8

Access Statistics for this chapter

More chapters in Springer Books from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().