On the proper orientation number of bipartite graphs
(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)
- author
- Araujo, Julio ; Cohen, Nathann ; de Rezende, Susanna F. LU ; Havet, Frédéric and Moura, Phablo F.S.
- publishing date
- 2015
- 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}}, }