1 |
One-sided interval edge-colorings of bipartite graphsRenman, Jonatan January 2020 (has links)
A graph is an ordered pair composed by a set of vertices and a set of edges, the latter consisting of unordered pairs of vertices. Two vertices in such a pair are each others neighbors. Two edges are adjacent if they share a common vertex. Denote the amount of edges that share a specific vertex as the degree of the vertex. A proper edge-coloring of a graph is an assignment of colors from some finite set, to the edges of a graph where no two adjacent edges have the same color. A bipartition (X,Y) of a set of vertices V is an ordered pair of two disjoint sets of vertices such that V is the union of X and Y, where all the vertices in X only have neighbors in Y and vice versa. A bipartite graph is a graph whose vertices admit a bipartition (X,Y). Let G be one such graph. An X-interval coloring of G is a proper edge coloring where the colors of the edges incident to each vertex in X form an interval of integers. Denote by χ'int(G,X) the least number of colors needed for an X-interval coloring of G. In this paper we prove that if G is a bipartite graph with maximum degree 3n (n is a natural number), where all the vertices in X have degree 3, then <img src="http://www.diva-portal.org/cgi-bin/mimetex.cgi?%5Cmathit%7B%5Cchi'_%7Bint%7D%5Cleft(G,X%5Cright)%5Cleq%7D%0A%5C%5C%0A%5Cmathit%7B%5Cleft(n-1%5Cright)%5Cleft(3n+5%5Cright)/2+3%7D%0A%5C%5C%0A%5Cmathit%7Bif%20n%20is%20odd,%7D%0A%5C%5C%0A%5Cmathit%7Bor%7D%0A%5C%5C%0A%5Cmathbf%7B3n%5E%7B2%7D/2+1%7D%0A%5C%5C%0A%5Cmathit%7Bif%20n%20is%20even%7D.%0A" />
|
2 |
On some graph coloring problemsCasselgren, Carl Johan January 2011 (has links)
No description available.
|
Page generated in 0.1353 seconds