IEICE TRANSACTIONS on Fundamentals
The Planar Hajós Calculus for Bounded Degree Graphs
Summary :
The planar Hajos calculus (PHC) is the Hajos calculus with the restriction that all the graphs that appear in the construction (including a final graph) must be planar. The degree-d planar Hajos calculus (PHC(dd)) is PHC with the restriction that all the graphs that appear in the construction (including a final graph) must have maximum degree at most d. We prove the followings: (1) If PHC is polynomially bounded, then for any d ≥ 4, PHC(dd+2) can generate any non-3-colorable planar graphs of maximum degree at most d in polynomial steps. (2) If PHC can generate any non-3-colorable planar graphs of maximum degree 4 in polynomial steps, then PHC is polynomially bounded.
- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E93-A No.6 pp.1000-1007
- Publication Date
- 2010/06/01
- Publicized
- Online ISSN
- 1745-1337
- DOI
- 10.1587/transfun.E93.A.1000
- Type of Manuscript
- Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
- Category
- Graphs and Networks
Authors
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Kazuo IWAMA, Kazuhisa SETO, Suguru TAMAKI, "The Planar Hajós Calculus for Bounded Degree Graphs" in IEICE TRANSACTIONS on Fundamentals,
vol. E93-A, no. 6, pp. 1000-1007, June 2010, doi: 10.1587/transfun.E93.A.1000.
Abstract: The planar Hajos calculus (PHC) is the Hajos calculus with the restriction that all the graphs that appear in the construction (including a final graph) must be planar. The degree-d planar Hajos calculus (PHC(dd)) is PHC with the restriction that all the graphs that appear in the construction (including a final graph) must have maximum degree at most d. We prove the followings: (1) If PHC is polynomially bounded, then for any d ≥ 4, PHC(dd+2) can generate any non-3-colorable planar graphs of maximum degree at most d in polynomial steps. (2) If PHC can generate any non-3-colorable planar graphs of maximum degree 4 in polynomial steps, then PHC is polynomially bounded.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.E93.A.1000/_p
Copy
@ARTICLE{e93-a_6_1000,
author={Kazuo IWAMA, Kazuhisa SETO, Suguru TAMAKI, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={The Planar Hajós Calculus for Bounded Degree Graphs},
year={2010},
volume={E93-A},
number={6},
pages={1000-1007},
abstract={The planar Hajos calculus (PHC) is the Hajos calculus with the restriction that all the graphs that appear in the construction (including a final graph) must be planar. The degree-d planar Hajos calculus (PHC(dd)) is PHC with the restriction that all the graphs that appear in the construction (including a final graph) must have maximum degree at most d. We prove the followings: (1) If PHC is polynomially bounded, then for any d ≥ 4, PHC(dd+2) can generate any non-3-colorable planar graphs of maximum degree at most d in polynomial steps. (2) If PHC can generate any non-3-colorable planar graphs of maximum degree 4 in polynomial steps, then PHC is polynomially bounded.},
keywords={},
doi={10.1587/transfun.E93.A.1000},
ISSN={1745-1337},
month={June},}
Copy
TY - JOUR
TI - The Planar Hajós Calculus for Bounded Degree Graphs
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 1000
EP - 1007
AU - Kazuo IWAMA
AU - Kazuhisa SETO
AU - Suguru TAMAKI
PY - 2010
DO - 10.1587/transfun.E93.A.1000
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E93-A
IS - 6
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - June 2010
AB - The planar Hajos calculus (PHC) is the Hajos calculus with the restriction that all the graphs that appear in the construction (including a final graph) must be planar. The degree-d planar Hajos calculus (PHC(dd)) is PHC with the restriction that all the graphs that appear in the construction (including a final graph) must have maximum degree at most d. We prove the followings: (1) If PHC is polynomially bounded, then for any d ≥ 4, PHC(dd+2) can generate any non-3-colorable planar graphs of maximum degree at most d in polynomial steps. (2) If PHC can generate any non-3-colorable planar graphs of maximum degree 4 in polynomial steps, then PHC is polynomially bounded.
ER -
English
