Boxicity of leaf powers

DOI10.1007/s00373-010-0962-5zbMath1234.05169arXiv0902.3551OpenAlexW2102429849MaRDI QIDQ659669

L. Sunil Chandran, Rogers Mathew, Mathew C. Francis

Publication date: 24 January 2012

Published in: Graphs and Combinatorics (Search for Journal in Brave)

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

zbMATH Keywords

interval graphsboxicitystrongly chordal graphsleaf powerstree powers

Mathematics Subject Classification ID

Applications of graph theory (05C90) Graph representations (geometric and intersection representations, etc.) (05C62)

Related Items

Boxicity of line graphs ⋮ Separability, boxicity, and partial orders

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Computing the boxicity of a graph by covering its complement by cointerval graphs
• Boxicity of circular arc graphs
• Structure and linear time recognition of 3-leaf powers
• Geometric representation of graphs in low dimension using axis parallel boxes
• Strictly chordal graphs are leaf powers
• Closest 4-leaf power is fixed-parameter tractable
• Boxicity of Halin graphs
• Characterizations of strongly chordal graphs
• Interval representations of planar graphs
• A characterization of strongly chordal graphs
• Chordal bipartite, strongly chordal, and strongly chordal bipartite graphs
• Boxicity and maximum degree
• Boxicity of series-parallel graphs
• Boxicity and treewidth
• On Graph Powers for Leaf-Labeled Trees
• Representation of a finite graph by a set of intervals on the real line
• On (k,ℓ)-Leaf Powers
• Strong clique trees, neighborhood trees, and strongly chordal graphs
• Structure and linear-time recognition of 4-leaf powers