Skip to Main content Skip to Navigation
Reports

Proper orientation of cacti

Julio Araujo 1 Frédéric Havet 2 Claudia Linhares Sales 1 Ana Silva 1
1 ParGO - Parallelism, Graphs and Optimization Research Group
2 COATI - Combinatorics, Optimization and Algorithms for Telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , Laboratoire I3S - COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
Abstract : An orientation of a graph is proper if two adjacent vertices have different indegrees. We prove that every cactus admits a proper orientation with maximum indegree at most 7. We also prove that the bound 7 is tight by showing a cactus having no proper orientation with maximum indegree less than 7. We also prove that any planar claw-free graph has a proper orientation with maximum indegree at most 6 and that this bound can also be attained.
Keywords : proper orientation graph coloring cactus graph claw-free graph
Document type :
Reports
Complete list of metadatas

Cited literature [9 references]  Display  Hide  Download
https://hal.inria.fr/hal-01247014
Contributor : Frederic Havet <>
Submitted on : Sunday, December 20, 2015 - 11:22:53 PM
Last modification on : Monday, October 12, 2020 - 10:30:39 AM
Long-term archiving on: : Saturday, April 29, 2017 - 10:58:28 PM

File

Vignette du document
RR-8833.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-01247014, version 1

Collections

CNRS | UNICE | INRIA | I3S | INRIA-RRRT | LARA | TDS-MACS | UNIV-COTEDAZUR

Citation

Julio Araujo, Frédéric Havet, Claudia Linhares Sales, Ana Silva. Proper orientation of cacti. [Research Report] RR-8833, INRIA Sophia Antipolis - Méditerranée. 2015, pp.17. ⟨hal-01247014⟩

Export

BibTeX TEI DC DCterms EndNote

Share

Metrics

Record views

831

Files downloads

643

 

Contact                    Legal Notice                    Personal Data