A note on path factors of (3,4)-biregular bipartite graphs
type: Item
instance of: scholarly article
title: A note on path factors of (3,4)-biregular bipartite graphs
zbMATH Open document ID: 1229.05225
author: Carl Johan Casselgren
published in: The Electronic Journal of Combinatorics
publication date: 2011-11-22T00:00:00Z
full work available at URL: v18i1p218.html
review text: Summary: A proper edge coloring of a graph \(G\) with colors \(1,2,3,\ldots\) is called an interval coloring if the colors on the edges incident with any vertex are consecutive. A bipartite graph is (3,4)-biregular if all vertices in one part have degree 3 and all vertices in the other part have degree 4. Recently it was proved [\textit{A. S. Asratian}, \textit{C.J. Casselgren}, \textit{J. Vandenbussche}, and \textit{D.B. West}, ``Proper path-factors and interval edge-coloring of (3,4)-biregular bigraphs,'' J. Graph Theory 61, No.\,2, 88--97 (2009; Zbl 1198.05037)] that if such a graph \(G\) has a spanning subgraph whose components are paths with endpoints at 3-valent vertices and lengths in \(\{2,4,6,8\}\), then \(G\) has an interval coloring. It was also conjectured that every simple (3,4)-biregular bipartite graph has such a subgraph. We provide some evidence for this conjecture by proving that a simple (3,4)-biregular bipartite graph has a spanning subgraph whose components are nontrivial paths with endpoints at 3-valent vertices and lengths not exceeding 22.
Mathematics Subject Classification ID: 05C70
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 05C38
zbMATH DE Number: 5976496
zbMATH Keywords: path factor
zbMATH Keywords: biregular bipartite graph
zbMATH Keywords: interval edge coloring
MaRDI profile type: Publication
description: scientific article; zbMATH DE number 5976496