On Linial's conjecture for spine digraphs

DOI10.1016/J.DISC.2016.12.017MaRDI QIDQ512554zbMATH OpenOpenAlexWikidataFDO

Authors Maycon Sambinelli, Cândida Nunes da Silva, Orlando Lee

Publication date 27 February 2017

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1606.06765

zbMATH Keywords

path partition\(k\)-partial coloringLinial's conjecturesplit digraph

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Coloring of graphs and hypergraphs (05C15) Paths and cycles (05C38) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: In this paper we introduce a superclass of split digraphs, which we call spine digraphs. Those are the digraphs D whose vertex set can be partitioned into two sets X and Y such that the subdigraph induced by X is traceable and Y is a stable set. We also show that Linial's Conjecture holds for spine digraphs.

Recommendations

• Proof of Berge's path partition conjecture for \(k \geq \lambda - 3\)
• The directed path partition conjecture
• Berge's conjecture and Aharoni-Hartman-Hoffman's conjecture for locally in-semicomplete digraphs
• The Path Partition Conjecture is true for some generalizations of tournaments
• Path partitions and packs of acyclic digraphs

Cites work

• scientific article; zbMATH DE number 3165195 (Why is no real title available?)
• scientific article; zbMATH DE number 3257176 (Why is no real title available?)
• A decomposition theorem for partially ordered sets
• Berge's conjecture on directed path partitions -- a survey
• Covering digraphs by paths
• Extending the Greene-Kleitman theorem to directed graphs
• Nombre chromatique et plus longs chemins d'un graphe
• On greene's theorem for digraphs
• Path partitions and packs of acyclic digraphs
• Proof of Berge's path partition conjecture for \(k \geq \lambda - 3\)
• Proof of Berge's strong path partition conjecture for \(k=2\)
• The structure of Sperner k-families
• k-optimal partitions of a directed graph

Cited in

(3)

• Linial's conjecture for arc-spine digraphs
• scientific article; zbMATH DE number 1145886 (Why is no real title available?)
• On the number of spikes concentrating on hyperplanes or line-segments to a Lin-Ni-Takagi problem

This page was built for publication: On Linial's conjecture for spine digraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q512554)