The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice
The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice
평면 Hajos 미적분학(PHC)는 구성에 나타나는 모든 그래프(최종 그래프 포함)가 평면이어야 한다는 제한이 있는 Hajos 미적분학입니다. 온도-d 평면 Hajos 미적분학(PHC(dd)) 이다 PHC 구성에 나타나는 모든 그래프(최종 그래프 포함)는 최대 차수를 가져야 한다는 제한이 있습니다. d. 우리는 다음을 증명합니다: (1) 만약 PHC 다항식 유계이고, 그러면 임의의 경우 d ≥ 4, PHC(dd+2) 최대 차수의 3색이 아닌 평면 그래프를 최대로 생성할 수 있습니다. d 다항식 단계에서. (2) 만일 PHC 다항식 단계에서 최대 3차의 4색이 아닌 평면 그래프를 생성할 수 있습니다. PHC 다항식으로 제한됩니다.
하요스 미적분학, 평면 그래프, 한정된 차수 그래프, 착색, 증명 시스템
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.
부
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
부
@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},}
부
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 -