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" />
| Identifer | oai:union.ndltd.org:UPSALLA1/oai:DiVA.org:liu-171753 |
| Date | January 2020 |
| Creators | Renman, Jonatan |
| Publisher | Linköpings universitet, Matematik och tillämpad matematik, Linköpings universitet, Tekniska fakulteten |
| Source Sets | DiVA Archive at Upsalla University |
| Language | English |
| Detected Language | English |
| Type | Student thesis, info:eu-repo/semantics/bachelorThesis, text |
| Format | application/pdf |
| Rights | info:eu-repo/semantics/openAccess |
Page generated in 0.0023 seconds