Institute for Theoretical Information Technology

How to find overfull subgraphs in graphs with large maximum degree

Authors

T. Niessen,

Abstract

        The existence of an overfull subgraph of a simple graph implies chi'=Delta +1, where chi' denotes the chromatic index and Delta the maximum degree. A linear time algorithm for finding the overfull subgraphs of simple graphs with 2*Delta >= |V| is presented. Thereby the chromatic index of many graphs can be determined in linear time.

BibT_EX Reference Entry 

@article{Ni94,
	author = {Thomas Niessen},
	title = "How to find overfull subgraphs in graphs with large maximum degree",
	pages = "117-125",
	journal = "Discrete Appl. Math.",
	volume = "51",
	year = 1994,
	hsb = RWTH-CONV-223136,
	}

Downloads

 _{Download bibtex-file}

Sorry, this paper is currently not available for download.