Computer Science – Discrete Mathematics
Scientific paper
2011-02-04
Computer Science
Discrete Mathematics
extended version of the paper "Hamiltonian alternating paths on bicolored double-chains" presented at Graph Drawing 2008
Scientific paper
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 has, 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 non-leaf 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.
Cibulka Josef
Kyncl Jan
Mészáros Viola
Stolař Rudolf
Valtr Pavel
No associations
LandOfFree
Universal Sets for Straight-Line Embeddings of Bicolored Graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Universal Sets for Straight-Line Embeddings of Bicolored Graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Universal Sets for Straight-Line Embeddings of Bicolored Graphs will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-491658