ضخامت

ضخامت (نظریه گراف). در نظریه گراف ضخامت گراف G، به حداقل تعداد گراف مسطحی که با یال های گراف G می توان ساخت گویند. به طوری که اگر k گراف مسطح وجود داشته باشد که همه شامل رئوس یکسانی باشد و حاصل اجتماع این گراف ها برابر G شود، آنگاه حداکثر عدد ضخامت این گراف k می باشد. به عبارت دیگر ضخامت گراف کمترین تعداد زیرگراف های مسطحی است که اجتماعشان برابر خود گراف باشد.
بنابر این ضخامت یک گراف مسطح برابر ۱ است. گراف هایی با ضخامت ۲ دو سطحی نامیده می شود. مفهوم ضخامت گراف از تخمین Frank Harary در سال ۱۹۶۲۲ نشات می گیرد: برای هر گرافی با درجه ۹ یا خودش یا مکملش غیر مسطح است. این مسیله معادل این است: تعیین این که ایا گراف کامل k9 دو سطحی است یا خیر (دو سطحی است و تخمین درست است)بررسی دقیقی در ۱۹۹۸ توسط Petra Mutzel ,Thomas odenthal وMark scharbrodr در این این زمینه صورت گرفته است.