EURO-Online login
- New to EURO? Create an account
- I forgot my username and/or my password.
- Help with cookies
(important for IE8 users)
3628. On the occurrence of optimally colored $K_{t,t}$ in canonical 1-factorizations of complete graphs
Invited abstract in session TA-25: Applications of combinatorial optimization I, stream Combinatorial Optimization.
Tuesday, 8:30-10:00Room: 011 (building: 208)
Authors (first author is the speaker)
| 1. | Sebastian Urrutia
|
| University Molde | |
| 2. | Dominique de Werra
|
| IMA, EPFL |
Abstract
Recoloring methods applied to optimally edge colored complete graphs of even size are fundamental components of local search procedures aiming to obtain 1-factorizations with specific properties. Then, there is an interest in finding in a 1-factorization, colored subgraphs that allow a local recoloring to obtain a new 1-factorization. The occurrence of bichromatic cycles, lanterns and optimally colored complete subgraphs in certain classes of 1-factorization has been previously studied. In this note we investigate the existence of optimally colored complete bipartite subgraphs in canonical 1-factorizations. We conclude that, whenever $n-1$ is a prime number, no optimally colored complete bipartite subgraphs with more than 4 nodes occur in canonical 1-factorizatoins of complete graphs with $n$ nodes. For other values of $n$ we show that optimally colored complete bipartite subgraphs with more than 4 nodes do occur and we show how to construct some of them. For some small bipartite subgraphs the construction given is proven to be unique.
Keywords
- Graphs and Networks
Status: accepted
Back to the list of papers