Skip to main content

Lund University Publications

LUND UNIVERSITY LIBRARIES

On the proper orientation number of bipartite graphs

Araujo, Julio ; Cohen, Nathann ; de Rezende, Susanna F. LU orcid ; Havet, Frédéric and Moura, Phablo F.S. (2015) In Theoretical Computer Science 566(C). p.59-75
Abstract

An orientation of a graph G is a digraph D obtained from G by replacing each edge by exactly one of the two possible arcs with the same endvertices. For each v∈V(G), the indegree of v in D, denoted by dD-(v), is the number of arcs with head v in D. An orientation D of G is proper if dD-(u)≠dD-(v), for all uv∈E(G). The proper orientation number of a graph G, denoted by χ→(G), is the minimum of the maximum indegree over all its proper orientations. In this paper, we prove that χ→(G)≤(δ(G)+√δ(G))/2+1 if G is a bipartite graph, and χ→(G)≤4 if G is a tree. It is well-known that χ→(G)≤δ(G), for every graph G. However, we prove that deciding whether χ→(G)≤δ(G)-1 is already an... (More)

An orientation of a graph G is a digraph D obtained from G by replacing each edge by exactly one of the two possible arcs with the same endvertices. For each v∈V(G), the indegree of v in D, denoted by dD-(v), is the number of arcs with head v in D. An orientation D of G is proper if dD-(u)≠dD-(v), for all uv∈E(G). The proper orientation number of a graph G, denoted by χ→(G), is the minimum of the maximum indegree over all its proper orientations. In this paper, we prove that χ→(G)≤(δ(G)+√δ(G))/2+1 if G is a bipartite graph, and χ→(G)≤4 if G is a tree. It is well-known that χ→(G)≤δ(G), for every graph G. However, we prove that deciding whether χ→(G)≤δ(G)-1 is already an NP-complete problem on graphs with δ(G). =. k, for every k ge; 3. We also show that it is NP-complete to decide whether χ→(G)≤2, for planar subcubic graphs G. Moreover, we prove that it is NP-complete to decide whether χ→(G)≤3, for planar bipartite graphs G with maximum degree 5.

(Less)
Please use this url to cite or link to this publication:
author
; ; ; and
publishing date
type
Contribution to journal
publication status
published
subject
keywords
Bipartite graph, Graph coloring, Proper orientation
in
Theoretical Computer Science
volume
566
issue
C
pages
17 pages
publisher
Elsevier
external identifiers
  • scopus:84926342816
ISSN
0304-3975
DOI
10.1016/j.tcs.2014.11.037
language
English
LU publication?
no
additional info
Funding Information: Research supported by CNPq -Brazil ( 477203/2012-4 ), FUNCAP /CNRS INC-0083-00047.01.00/13 , FAPESP -Brazil (Proc. 2011/16348-0 , 2013/19179-0 , 2013/03447-6 ) and ANR Blanc STINT ANR-13-BS02-0007-03 . Publisher Copyright: © 2014 Elsevier B.V.
id
c95ce323-adbe-403d-b575-5392afd6d5d4
date added to LUP
2021-12-17 11:53:42
date last changed
2022-04-27 07:00:44
@article{c95ce323-adbe-403d-b575-5392afd6d5d4,
  abstract     = {{<p>An orientation of a graph G is a digraph D obtained from G by replacing each edge by exactly one of the two possible arcs with the same endvertices. For each v∈V(G), the indegree of v in D, denoted by d<sup>D</sup><sub>-</sub>(v), is the number of arcs with head v in D. An orientation D of G is proper if d<sup>D</sup><sub>-</sub>(u)≠d<sup>D</sup><sub>-</sub>(v), for all uv∈E(G). The proper orientation number of a graph G, denoted by χ→(G), is the minimum of the maximum indegree over all its proper orientations. In this paper, we prove that χ→(G)≤(δ(G)+√δ(G))/2+1 if G is a bipartite graph, and χ→(G)≤4 if G is a tree. It is well-known that χ→(G)≤δ(G), for every graph G. However, we prove that deciding whether χ→(G)≤δ(G)-1 is already an NP-complete problem on graphs with δ(G). =. k, for every k ge; 3. We also show that it is NP-complete to decide whether χ→(G)≤2, for planar subcubic graphs G. Moreover, we prove that it is NP-complete to decide whether χ→(G)≤3, for planar bipartite graphs G with maximum degree 5.</p>}},
  author       = {{Araujo, Julio and Cohen, Nathann and de Rezende, Susanna F. and Havet, Frédéric and Moura, Phablo F.S.}},
  issn         = {{0304-3975}},
  keywords     = {{Bipartite graph; Graph coloring; Proper orientation}},
  language     = {{eng}},
  number       = {{C}},
  pages        = {{59--75}},
  publisher    = {{Elsevier}},
  series       = {{Theoretical Computer Science}},
  title        = {{On the proper orientation number of bipartite graphs}},
  url          = {{http://dx.doi.org/10.1016/j.tcs.2014.11.037}},
  doi          = {{10.1016/j.tcs.2014.11.037}},
  volume       = {{566}},
  year         = {{2015}},
}