✦ LIBER ✦

Short Solution of Kotzig's Problem for Bipartite Graphs

✍ Scribed by A.S. Asratian

Publisher: Elsevier Science
Year: 1998
Tongue: English
Weight: 263 KB
Volume: 74
Category: Article
ISSN: 0095-8956
DOI: 10.1006/jctb.1998.1838

No coin nor oath required. For personal study only.

✦ Synopsis

In 1975, A. Kotzig posed the following problem: Let G be a t-regular graph which has a proper edge t-coloring, t 4. Is it possible to obtain, from one proper edge t-coloring of G, any other proper edge t-coloring of G using only transformations of 2-colored and 3-colored subgraphs such that the intermediate colorings are also proper? The author and A. N. Mirumian proved that it is possible if G is a bipartite graph. We give here a short proof of this result.

📜 SIMILAR VOLUMES

An extremal bandwidth problem for bipart

An extremal bandwidth problem for bipartite graphs

✍ Robert C. Brigham; Julie R. Carrington; Ronald D. Dutton; Joseph Fiedler; Richar 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 119 KB 👁 2 views

On the Ramsey Problem for Multicolor Bip

On the Ramsey Problem for Multicolor Bipartite Graphs

✍ W.A Carnielli; E.L Monte Carmelo 📂 Article 📅 1999 🏛 Elsevier Science 🌐 English ⚖ 85 KB

Given i, j positive integers, let K denote a bipartite complete graph and let i, j ## Ž . R m, n be the smallest integer a such that for any r-coloring of the edges of K r a, a one can always find a monochromatic subgraph isomorphic to K . In other m, n Ž . Ä 4 words, if a G R m, n then every mat

A Short Proof of Guenin's Characterizati

A Short Proof of Guenin's Characterization of Weakly Bipartite Graphs

✍ Alexander Schrijver 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 79 KB

We give a proof of Guenin's theorem characterizing weakly bipartite graphs by not having an odd-K 5 minor. The proof curtails the technical and case-checking parts of Guenin's original proof.

NP completeness of the edge precoloring

NP completeness of the edge precoloring extension problem on bipartite graphs

✍ Jiří Fiala 📂 Article 📅 2003 🏛 John Wiley and Sons 🌐 English ⚖ 63 KB 👁 1 views

## Abstract We show that the following problem is __NP__ complete: Let __G__ be a cubic bipartite graph and __f__ be a precoloring of a subset of edges of __G__ using at most three colors. Can __f__ be extended to a proper edge 3‐coloring of the entire graph __G__? This result provides a natural co

Solution of fink & straight conjecture o

Solution of fink & straight conjecture on path-perfect complete bipartite graphs

✍ Weiting Cao; Peter Hamburger 📂 Article 📅 2007 🏛 John Wiley and Sons 🌐 English ⚖ 213 KB 👁 1 views

## Abstract We consider various edge disjoint partitions of complete bipartite graphs. One case is where we decompose the edge set into edge disjoint paths of increasing lengths. A graph __G__ is __path‐perfect__ if there is a positive integer __n__ such that the edge set __E__(__G__) of the graph

The Solution of a Problem of Godsil on C

The Solution of a Problem of Godsil on Cubic Cayley Graphs

✍ Cai Heng Li 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 267 KB

In this short paper, we give a positive answer to a question of C. D. Godsil (1983, Europ. J. Combin. 4, 25 32) regarding automorphisms of cubic Cayley graphs of 2-groups: ``If Cay(G, S) is a cubic Cayley graph of a 2-group G and A=Aut Cay(G, S), does A 1 {1 imply Aut(G, S){1?'' 1998 Academic Press