Graph orientations with edge-connection and parity constraints
type: Item
instance of: scholarly article
title: Graph orientations with edge-connection and parity constraints
zbMATH Open document ID: 0989.05099
author: András Frank
author: Zoltán Király
published in: Combinatorica
publication date: 2002-06-25T00:00:00Z
review text: For a graph \(G=(V,E)\), we say \(T\subseteq V\) is \(G\)-even if \(|T|+|E|\) is even. An orientation of \(G\) is \(T\)-odd if the in-degree of a node \(v\) is odd precisely when \(v\in T\). The main result of this paper is an NP and co-NP characterization of graphs admitting the property `\(G\) has an \(l\)-edge-connected \(T\)-odd orientation for every \(G\)-even subset \(T\) of nodes'. As a corollary it is also shown that every \(4\)-edge-connected graph \(G=(V,E)\) with a \(G\)-even subset \(T\) has a strongly connected \(T\)-odd orientation. Several related results combining parity and connectivity requirements are imposed.
Mathematics Subject Classification ID: 05C75
Mathematics Subject Classification ID: 05C40
zbMATH DE Number: 1759189
zbMATH Keywords: connectivity
zbMATH Keywords: orientation
MaRDI profile type: Publication
full work available at URL: s004930200003
OpenAlex ID: W1984188921
DOI: 10.1007/S004930200003
description: scientific article; zbMATH DE number 1759189