Document Type
Lecture
Publication Date
7-27-2009
Abstract
An edge-coloring of a graph is an assignment of an integer (called color) to every edge so that adjacent edges get different colors. An edge-coloring that uses k different colors is k-linear compact if the colors incident to every vertex are consecutive in {0, · · · , k−1}. The problem k−LCCP is to determine whether a given graph admits a k-linear compact edge coloring. An edge-coloring is k-cyclic compact if there are two positive integers av, bv in {0, · · · , k−1} for every vertex v such that the colors incident to v are exactly {av, (av + 1)mod k, · · · , bv}. The problem k−CCCP is to determine whether a given graph admits a k-cyclic compact edge coloring. We show that the k−LCCP with possibly imposed or forbidden colors on some edges is polynomially reducible to the k−CCCP when k ≥ 12, and to the 12−CCCP when k < 12.
Relational Format
presentation
Recommended Citation
Altinakar, Sivan, "On compact edge-colorings : a polynomial time reduction from k-linear to k-cyclic" (2009). Combinatorics Seminar. 80.
https://egrove.olemiss.edu/math_combinatorics/80
