On Linial's conjecture for spine digraphs

DOI10.1016/J.DISC.2016.12.017zbMATH Open1357.05054arXiv1606.06765OpenAlexW2963699585WikidataQ123195305 ScholiaQ123195305MaRDI QIDQ512554FDOQ512554

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

Publication date: 27 February 2017

Published in: Discrete Mathematics (Search for Journal in Brave)

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.

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

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

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)

Cites Work

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

Cited In (3)

• Linial's conjecture for arc-spine digraphs
• Title not available (Why is that?)
• 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)