A short proof of the degree bound for interval number

DOI10.1016/0012-365X(89)90276-8MaRDI QIDQ1114708zbMATH OpenFDO

Authors Douglas B. West

Publication date 1989

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0012-365X(89)90276-8

zbMATH Keywords

interval representation

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Graph theory (05C99)

Review text

A short proof is given of the fact that every graph has an interval representation of depth 2 in which each vertex v is represented by at most \(\lfloor (d(v)+1\rfloor\) intervals, except for an arbitrarily specified vertex w that appears left-most in the representation and is represented by at most \(\lceil (d(w)+1)\rceil\) intervals.

Recommendations

• scientific article; zbMATH DE number 1011262
• Short proofs for interval digraphs
• A short proof of a theorem on degree sets of graphs
• A lower bound for the interval number of a graph
• Two short proofs of the bounded case of S. B. Rao's degree sequence conjecture
• Some results about the interval number of a graph
• Short interval results for a class of integers
• A Short Proof of a Theorem of Erdos and Mordell
• A Short Proof of the Erdos-Mordell Theorem
• An Interval of Computably Enumerable Isolating Degrees

Cites work

• Extremal Values of the Interval Number of a Graph

Cited in

(7)

• On a complementary interval graph with the lowest max-degree
• Interval numbers of powers of block graphs
• Recognizing d-interval graphs and d-track interval graphs
• An improved edge bound on the interval number of a graph
• On the interval number of special graphs
• Subtree and substar intersection numbers
• Three ways to cover a graph

This page was built for publication: A short proof of the degree bound for interval number

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