Interval Edge-Colorings of Graphs

Date Issued:: 2016
Abstract/Description:: A proper edge-coloring of a graph G by positive integers is called an interval edge-coloring if the colors assigned to the edges incident to any vertex in G are consecutive (i.e., those colors form an interval of integers). The notion of interval edge-colorings was first introduced by Asratian and Kamalian in 1987, motivated by the problem of finding compact school timetables. In 1992, Hansen described another scenario using interval edge-colorings to schedule parent-teacher conferences so that every person's conferences occur in consecutive slots. A solution exists if and only if the bipartite graph with vertices for parents and teachers, and edges for the required meetings, has an interval edge-coloring.A well-known result of Vizing states that for any simple graph $G$, $\chi'(G) \leq \Delta(G) + 1$, where $\chi'(G)$ and $\Delta(G)$ denote the edge-chromatic number and maximum degree of $G$, respectively. A graph $G$ is called class 1 if $\chi'(G) = \Delta(G)$, and class 2 if $\chi'(G) = \Delta(G) + 1$. One can see that any graph admitting an interval edge-coloring must be of class 1, and thus every graph of class 2 does not have such a coloring.Finding an interval edge-coloring of a given graph is hard. In fact, it has been shown that determining whether a bipartite graph has an interval edge-coloring is NP-complete. In this thesis, we survey known results on interval edge-colorings of graphs, with a focus on the progress of $(a, b)$-biregular bipartite graphs. Discussion of related topics and future work is included at the end. We also give a new proof of Theorem 3.15 on the existence of proper path factors of $(3, 4)$-biregular graphs. Finally, we obtain a new result, Theorem 3.18, which states that if a proper path factor of any $(3, 4)$-biregular graph has no path of length 8, then it contains paths of length 6 only. The new result we obtained and the method we developed in the proof of Theorem 3.15 might be helpful in attacking the open problems mentioned in the Future Work section of Chapter 5.

Title:	Interval Edge-Colorings of Graphs.	37 views 17 downloads
Name(s):	Foster, Austin, Author Song, Zixia, Committee Chair Reid, Michael, Committee Member Brennan, Joseph, Committee Member University of Central Florida, Degree Grantor
Type of Resource:	text
Date Issued:	2016
Publisher:	University of Central Florida
Language(s):	English
Abstract/Description:	A proper edge-coloring of a graph G by positive integers is called an interval edge-coloring if the colors assigned to the edges incident to any vertex in G are consecutive (i.e., those colors form an interval of integers). The notion of interval edge-colorings was first introduced by Asratian and Kamalian in 1987, motivated by the problem of finding compact school timetables. In 1992, Hansen described another scenario using interval edge-colorings to schedule parent-teacher conferences so that every person's conferences occur in consecutive slots. A solution exists if and only if the bipartite graph with vertices for parents and teachers, and edges for the required meetings, has an interval edge-coloring.A well-known result of Vizing states that for any simple graph $G$, $\chi'(G) \leq \Delta(G) + 1$, where $\chi'(G)$ and $\Delta(G)$ denote the edge-chromatic number and maximum degree of $G$, respectively. A graph $G$ is called class 1 if $\chi'(G) = \Delta(G)$, and class 2 if $\chi'(G) = \Delta(G) + 1$. One can see that any graph admitting an interval edge-coloring must be of class 1, and thus every graph of class 2 does not have such a coloring.Finding an interval edge-coloring of a given graph is hard. In fact, it has been shown that determining whether a bipartite graph has an interval edge-coloring is NP-complete. In this thesis, we survey known results on interval edge-colorings of graphs, with a focus on the progress of $(a, b)$-biregular bipartite graphs. Discussion of related topics and future work is included at the end. We also give a new proof of Theorem 3.15 on the existence of proper path factors of $(3, 4)$-biregular graphs. Finally, we obtain a new result, Theorem 3.18, which states that if a proper path factor of any $(3, 4)$-biregular graph has no path of length 8, then it contains paths of length 6 only. The new result we obtained and the method we developed in the proof of Theorem 3.15 might be helpful in attacking the open problems mentioned in the Future Work section of Chapter 5.
Identifier:	CFE0006301 (IID), ucf:51609 (fedora)
Note(s):	2016-08-01 M.S. Sciences, Mathematics Masters This record was generated from author submitted information.
Subject(s):	graph theory -- interval edge-coloring -- compact scheduling -- biregular graph
Persistent Link to This Record:	http://purl.flvc.org/ucf/fd/CFE0006301
Restrictions on Access:	public 2016-08-15
Host Institution:	UCF

In Collections

ETD Collection

Search In

You are here

In Collections